#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &p) {
  os << "[ ";
  for (auto &it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const unordered_set<T> &p) {
  os << "[ ";
  for (auto &it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &p) {
  os << "[ ";
  for (auto &it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const multiset<T> &p) {
  os << "[ ";
  for (auto &it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class S, class T>
ostream &operator<<(ostream &os, const unordered_map<S, T> &p) {
  os << "[ ";
  for (auto &it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const map<S, T> &p) {
  os << "[ ";
  for (auto &it : p) os << it << " ";
  return os << "]";
}
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... S>
void dbs(string str, T t, S... s) {
  long long idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ", ";
  dbs(str.substr(idx + 1), s...);
}
long long modExp(long long x, long long y, long long mod) {
  x %= mod, y %= (mod - 1);
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % mod;
    y /= 2, x = (x * x) % mod;
  }
  return res % mod;
}
long long cel(long long num, long long den) {
  if (num % den == 0)
    return num / den;
  else
    return 1 + num / den;
}
void dfs(long long node, vector<vector<long long> > &g, vector<long long> &ans,
         vector<long long> &col_visit, vector<long long> &c,
         vector<long long> &vis) {
  vis[node] = 1;
  if (col_visit[c[node]] == 0) {
    ans.push_back(node);
    col_visit[c[node]] = 1;
  }
  for (auto x : g[node]) {
    if (not vis[x]) {
      bool colored = col_visit[c[x]];
      dfs(x, g, ans, col_visit, c, vis);
      if (not colored)
        col_visit[c[x]] = 0;
      else
        col_visit[c[x]] = 1;
    }
  }
}
map<string, long long> dp;
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long testcases;
  cin >> testcases;
  for (long long testcase = 1; testcase <= testcases; testcase++) {
    string s;
    long long m;
    cin >> s >> m;
    sort((s).begin(), (s).end());
    if (dp.find(s) != dp.end()) {
      cout << dp[s] << '\n';
      continue;
    }
    vector<long long> f(2e5 + 200, 0);
    long long mod = 1e9 + 7;
    for (long long i = 0; i < (long long)(s).size(); i++) {
      long long val = '9' - s[i] + 1;
      {};
      f[val]++;
    }
    f[0] = 0;
    for (long long i = 1; i <= m; i++) {
      f[i + 9] = (f[i + 9] + f[i]) % mod;
      f[i + 10] = (f[i + 10] + f[i]) % mod;
      f[i] = (f[i] + f[i - 1]) % mod;
      {};
    }
    dp[s] = ((long long)(s).size() + f[m]) % mod;
    cout << dp[s] << '\n';
  }
}
