#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
using namespace std;
long long MOD = 1000000007;
double eps = 1e-12;
long long func(long long dp[], long long totTurns) { return dp[totTurns]; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  long long* arr = new long long[300000];
  for (long long i = 0; i < 9; i++) arr[i] = 2;
  arr[9] = 3;
  for (long long i = 10; i < 300000; i++) arr[i] = arr[i - 10] + arr[i - 9];
  cin >> t;
  while (t--) {
    string s;
    long long k;
    cin >> s >> k;
    long long count = 0;
    for (long long i = 0; i < s.length(); i++) {
      int num = s[i] - '0';
      int turns = 10 - num;
      int turnsLeft = k - turns;
      count = turnsLeft < 0 ? (count % MOD + 1 % MOD) % MOD
                            : (count % MOD + arr[turnsLeft] % MOD) % MOD;
    }
    cout << count << endl;
  }
  return 0;
}
