#include <bits/stdc++.h>
using namespace std;
long long hi[200001];
signed main() {
  hi[0] = 2;
  hi[1] = 2;
  hi[2] = 2;
  hi[3] = 2;
  hi[4] = 2;
  hi[5] = 2;
  hi[6] = 2;
  hi[7] = 2;
  hi[8] = 2;
  hi[9] = 3;
  hi[10] = 4;
  hi[11] = 4;
  hi[12] = 4;
  hi[13] = 4;
  hi[14] = 4;
  hi[15] = 4;
  hi[16] = 4;
  hi[17] = 4;
  hi[18] = 5;
  hi[19] = 7;
  hi[20] = 8;
  ios_base::sync_with_stdio(false);
  for (long long i = 21; i <= 200000; i++)
    hi[i] = (hi[i - 9] + hi[i - 10]) % 1000000007;
  long long testis;
  cin >> testis;
  while (testis--) {
    long long ans = 0;
    long long n, m;
    cin >> n >> m;
    while (n > 0) {
      long long x = n % 10 + m;
      ans += ((x < 10) ? 1 : hi[x - 10]);
      n /= 10;
    }
    cout << ans << endl;
  }
  return 0;
}
