#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#define Arr std::vector
#define Ptn std::pair
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
const int N = 1e3 + 5;
const int M = 9e3 + 5;
const int P = 1e9 + 7;
int T, n, k, m, f[N][M], t[2][M], op[M];
std::string s;

inline void Add(int &x, int y) { x += y; if (x >= P) x -= P; }

int dfs(int p, bool lim, int sum)
{
    if (p == n + 1) return (sum == 0);
    if (!lim && f[p][sum] != -1) return f[p][sum];
    int up = std::min(sum, (lim ? s[p] - '0' : 9)), res = 0;
    for (register int i = 0; i <= up; i++) Add(res, dfs(p + 1, lim && (i == (s[p] - '0')), sum - i));
    if (!lim) f[p][sum] = res;
    return res; 
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> T;
    for (int i = 0; i < M; i++)
    {
        int x = i, cnt = 0; 
        while (x)
        {
            cnt += (x % 10);
            x /= 10;
        }
        op[i] = cnt;
    }
    while (T--)
    {
        // memset(t, 0, sizeof(t));
        memset(f, -1, sizeof(f));
        std::cin >> s; n = s.size(); s = " " + s;
        std::cin >> k >> m; 
        if (m > 9000) { printf("0\n"); continue; }
        int kel = 0;
        for (int i = 0; i <= 9000; i++) t[kel][i] = dfs(1, true, i); k--;
        // for (int i = 0; i <= 20; i++) printf("%lld ", t[kel][i]); printf("\n");
        k = std::min(4, k);
        for (int i = 1; i <= k; i++)
        {
            kel ^= 1; memset(t[kel], 0, sizeof(t[kel]));
            for (int j = 0; j <= 9000; j++) Add(t[kel][op[j]], t[kel ^ 1][j]);
        }
        std::cout << t[kel][m] << '\n';
    }
   
    return 0;
}