#include <bits/stdc++.h>

void Yes() {
    std::cout << "YES" << "\n";
    return;
}

void No() {
    std::cout << "NO" << "\n";
    return;
}

template<typename T>
void out(T x) { std::cout << x << "\n"; }

using namespace std;
using ll = long long;
using PII = pair<ll, ll>;

const ll N = 2e5 + 10;

ll k, m;
string n;
ll a[1005];
ll dp[1004][9004];
const int mod = 1e9 + 7;
//ll tong[9001];
ll cc(ll x) {
    ll tmp = 0;
    while (x) {
        tmp += x % 10;
        x /= 10;
    }
    return tmp;
}

ll dfs(ll pos, ll sum, ll lim, ll lead0) {
    if (pos == 0) {

        for (ll i = 1; i <= k - 1; i++) {
            sum = cc(sum);
        }
        return sum == m;
    }

    if (!lim && !lead0 && dp[pos][sum] != -1) {
        return dp[pos][sum];
    }
    ll up = lim ? a[pos] : 9;
    ll tmp = 0;
    for (ll i = 0; i <= up; i++) {
        tmp += dfs(pos - 1, sum + i, lim && (i == up), lead0 && (i == 0));
        tmp%=mod;
    }
    if (!lim && !lead0) {
        return dp[pos][sum] = tmp;
    }
    return tmp;
}

ll cal(string s) {
    ll len = 0;
    reverse(s.begin(), s.end());
    for (auto p: s) {
        a[++len] = p - '0';
    }
    return dfs(len, 0, 1, 1);
}

void Solve() {
    for (ll i = 0; i <= 1002; i++)
        for (ll j = 0; j <= 9001; j++)
            dp[i][j] = -1;
    cin >> n >> k >> m;
    k = min(k, 5ll);
    cout << cal(n) <<"\n";
//    for(ll i = 1;i<=20;i++) {
//        cout<<tong[i]<<"\n";
//    }
}

signed main() {

    ll t = 1;
    cin>>t;
    while (t--)
        Solve();
}