#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define MULT_TEST 1
using namespace std;
const int MOD = 1000000007;
const int N = 1002, M = 9002;
int n, dp[N][M], mp[M];
char st[N];
vector<pair<int, int>> E;
inline int read() {
    int w = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        w = (w << 1) + (w << 3) + ch - 48;
        ch = getchar();
    }
    return w;
}
inline int Find(int x) {
    int res = 0;
    while (x) {
        res += (x % 10);
        x /= 10;
    }
    return res;
}
inline int DFS(int s, int t, int op) {
    if (s > n) return (mp[t] ? 1 : 0);
    if (!op && dp[s][t] != -1) return dp[s][t];
    int res = 0;
    for (int i = 0; i <= 9; i++) {
        if (op && i > st[s] - '0') continue;
        res += DFS(s + 1, t + i, op & (i == st[s] - '0'));
        if (res >= MOD) res -= MOD;
    }
    if (!op) dp[s][t] = res;
    return res;
}
inline void Solve() {
    int k, m;
    scanf("%s", st + 1);
    k = read(); m = read();
    if (m > 9000) return printf("0\n"), void();
    if (k >= 2 && m > 36) return printf("0\n"), void();
    for (int i = 1; i <= 9000; i++) {
        int c = i;
        for (int j = 1; j < k; j++) {
            c = Find(c);
            if (c < 10) break;
        }
        if (c == m) mp[i] = 1;
        else mp[i] = 0;
    }
    n = strlen(st + 1);
    memset(dp, -1, sizeof(dp));
    printf("%d\n", DFS(1, 0, 1));
}
signed main() {
    int _ = 1;
#if MULT_TEST
    _ = read();
#endif 
    while (_--) Solve();
    return 0;
}