//by 72
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
// #define int long long
using namespace std;

const int mod = 1e9 + 7;
const int N = 2e5 + 10;
// const int inf = 1e18;
typedef array<int, 3> a3; 
typedef long long ll;

int n, m, k;
int f[2][1005][10005], v[2][1005][10005]; // f[i][j][k] 表示还剩j位没填 剩下的和为i 贴不贴上界的方案数

string s;
void add(int &x, int y) {if((x += y) >= mod) x -= mod;}
void del(int &x, int y) {if((x -= y) < 0) x += mod;}

int dfs(int lst, int sum, int up) {
    if(sum < 0) return 0;
    if(lst == 0) return sum == 0;
    if(v[up][lst][sum]) return f[up][lst][sum];

    int ans = 0;
    int now = s[n + 1 - lst] - '0';
    if(up == 1) {
        add(ans, dfs(lst - 1, sum - now, 1));
        F(i, 0, now - 1) add(ans, dfs(lst - 1, sum - i, 0));
    } else {
        F(i, 0, 9) add(ans, dfs(lst - 1, sum - i, 0));
    }
    v[up][lst][sum] = 1;
    return f[up][lst][sum] = ans;
}

int get(int x) {
    F(i, 1, min(k - 1, 10)) {
        int sum = 0;
        while(x) sum += x % 10, x /= 10;
        x = sum;
    }
    return x;
}

void sol() {
    cin >> s >> k >> m;
    n = s.size(), s = " " + s;
    memset(f, 0, sizeof(f));
    memset(v, 0, sizeof(v));
    int res = 0;
    F(i, 1, 9000) if(get(i) == m) {
        add(res, dfs(n, i, 1));
    }
    cout << res << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    F(i, 1, t) sol();
    return 0;
}
//sldl