#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
vector<long long> graph[100001];
long long A[1000001];
long long B[1000001];
long long con[1000001];
long long a[100001];
long long b[100001];
long long par[100001];
long long h[100001];
long long vis[100001];
long long M = 1e5 + 1;
long long dp[10][1000001];
vector<long long> sset;
priority_queue<pair<long long, long long>> LT;
long long n, s;
long long TEMP;
void solve1(long long SUP, long long d) {
  vis[SUP]++;
  h[SUP] = d;
  bool is_it = true;
  for (long long chd : graph[SUP]) {
    if (!vis[chd]) {
      par[chd] = SUP;
      solve1(chd, d + 1);
      is_it = false;
    }
  }
  if (is_it == true) {
    LT.push({d, SUP});
  }
}
void done() {
  for (long long i = 0; i < n + 1; i++) {
    graph[i].clear();
    a[i] = 0;
    b[i] = 0;
    par[i] = 0;
    h[i] = 0;
  }
  while (!LT.empty()) {
    LT.pop();
  }
}
void clean(long long sup) {
  con[a[sup]] = 0;
  con[b[sup]] = 0;
  A[a[sup]] = 0;
  B[a[sup]] = 0;
  A[b[sup]] = 0;
  B[b[sup]] = 0;
}
int solve2(long long sup) {
  B[b[sup]]++;
  A[a[sup]]++;
  if (A[a[sup]] == B[a[sup]] && con[a[sup]] != 0) {
    con[a[sup]]--;
    TEMP--;
  } else if (con[a[sup]] == 0) {
    con[a[sup]]++;
    TEMP++;
  }
  if (A[b[sup]] == B[b[sup]] && con[b[sup]] != 0) {
    con[b[sup]]--;
    TEMP--;
  } else if (con[b[sup]] == 0) {
    con[b[sup]]++;
    TEMP++;
  }
  vis[sup]++;
  sset.push_back(sup);
  if (TEMP == 0) {
    if (vis[par[sup]] == 0 && sup != 1)
      LT.push(make_pair(h[par[sup]], par[sup]));
    clean(sup);
    return 1;
  }
  if (sup == 1) {
    clean(sup);
    return 0;
  }
  if (vis[par[sup]] == 0) {
    if (solve2(par[sup]) == 1) {
      clean(sup);
      return 1;
    }
  }
  clean(sup);
  return 0;
}
int sol() {
  cin >> n >> s;
  for (long long i = 0; i < n - 1; i++) {
    long long u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  for (long long i = 1; i < n + 1; i++) {
    cin >> a[i];
  }
  for (long long i = 1; i < n + 1; i++) {
    cin >> b[i];
  }
  for (long long i = 1; i < n + 1; i++) {
    vis[i] = 0;
    par[i] = 0;
    h[i] = 0;
  }
  solve1(1, 1);
  for (long long i = 1; i < n + 1; i++) {
    vis[i] = 0;
  }
  bool correct = true;
  vector<vector<long long>> sets;
  while (!LT.empty()) {
    pair<long long, long long> lesf = LT.top();
    LT.pop();
    if (vis[lesf.second] == 0) {
      TEMP = 0;
      sset.clear();
      if (solve2(lesf.second) == 0) {
        correct = false;
        break;
      } else {
        sets.push_back(sset);
      }
    }
  }
  if (correct == false) {
    cout << 0 << endl;
    return 0;
  }
  if (s == 1) {
    cout << 1 << endl;
    return 0;
  }
  long long a = 1;
  long long x = sets.size();
  for (long long i = 0; i < x; i++) {
    long long u = sets[i][0];
    long long l = sets[i][0];
    long long sze = sets[i].size();
    for (long long j = 1; j < sze; j++) {
      if (h[sets[i][j]] > h[l]) l = sets[i][j];
      if (h[sets[i][j]] < h[u]) u = sets[i][j];
    }
    long long cnt = 0;
    for (long long c : graph[l]) {
      if (c != par[l]) cnt++;
    }
    a = (a * (cnt + 1)) % mod;
  }
  cout << a << endl;
  return 0;
}
string Binary(int n) {
  string s = bitset<64>(n).to_string();
  const auto loc1 = s.find('1');
  if (loc1 != string::npos) {
    return s.substr(loc1);
  }
  return 0;
}
void solve() {
  string n;
  int m;
  cin >> n >> m;
  map<char, long long> mp;
  for (int i = 0; i < n.length(); i++) {
    mp[n[i]]++;
  }
  long long ans = 0;
  for (auto i : mp) {
    long long temp = i.first - '0';
    long long occ = i.second;
    ans += occ * dp[temp][m];
  }
  cout << ans << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  for (int i = 0; i <= 9; i++) {
    dp[i][0] = 1;
  }
  for (int j = 1; j <= 1e5; j++) {
    for (int i = 0; i <= 9; i++) {
      if (i <= 8)
        dp[i][j] = dp[i + 1][j - 1];
      else {
        dp[i][j] = (dp[0][j - 1] + dp[1][j - 1]) % mod;
      }
    }
  }
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
