#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int f[200010];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 0; i < 200010; i++) {
    if (i < 9)
      f[i] = 2;
    else if (i == 9)
      f[i] = 3;
    else
      f[i] = f[i - 9] + f[i - 10];
  }
  int t;
  cin >> t;
  while (t--) {
    string s;
    int m;
    cin >> s >> m;
    long long ans = 0;
    for (int i = 0; i < s.size(); i++) {
      ans = (ans + ((m + (s[i] - '0') < 10) ? 1 : f[m - (10 - (s[i] - '0'))])) %
            MOD;
    }
    cout << ans << endl;
  }
  return 0;
}
