// https://qoj.ac/contest/1464/problem/7996
// 1次f最大达到9000（sum 10^1000-1）
// 2次f最大达到35（sum 8999）
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int M = 9e3 + 5;
const int N = 1e3 + 5;
int dp[N][M], mp[M];
string str;
int k, m, n;
int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
void write(int x) {
    if (x < 0)
    {
        x = -x;
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int SUM(int x) {
    int res = 0;
    while (x) {
        res += (x % 10);
        x /= 10;
    }
    return res;
}
int dfs(int p, int s, bool reach_up) { // p for position, s for sum
    // reach_up for str[p-1] have reached upper limit or not
    if (p == n) return mp[s];
    if (p > n) return 0;
    if (!reach_up && dp[p][s] != -1) return dp[p][s];
    ll res = 0;
    for (int i = 0; i <= 9; i++) {
        if (reach_up && str[p] - '0' < i) continue;
        res += dfs(p + 1, s + i, reach_up & (str[p] - '0' == i));
        res %= mod;
    }
    if (!reach_up) dp[p][s] = res;
    return res;
}
void solve() {
    cin >> str;
    k = read(), m = read();
    if ((m > 9000) || (k >= 2 && m >= 36)) {
        cout << 0 << '\n';
        return;
    }
    n = str.length();
    for (int i = 1; i <= 9000; i++) {
        int x = i;
        for (int i = 1; i < k; i++) {
            x = SUM(x);
            if (x < 10) break;
        }
        if (x == m) mp[i] = 1;
        else mp[i] = 0;
    }
    memset(dp, -1, sizeof(dp));
    write(dfs(0, 0, 1));
    cout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}