#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MOD = 1e9+7;

// 计算数字n的各位数字之和
int digitSum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// 计算g(n, k)函数
int g(int n, int k) {
    for (int i = 0; i < k; ++i) {
        n = digitSum(n);
    }
    return n;
}

// 计算在不超过N的正整数中满足g(n, k) = m的数的个数
int countUnreportableNumbers(int N, int k, int m) {
    int count = 0;
    for (int n = 1; n <= N; ++n) {
        if (g(n, k) == m) {
            ++count;
        }
    }
    return count;
}

int main() {
    int T;
    cin >> T;
    vector<int> results(T);

    for (int i = 0; i < T; ++i) {
        int N, k, m;
        cin >> N >> k >> m;
        results[i] = countUnreportableNumbers(N, k, m);
    }

    for (const auto& result : results) {
        cout << result % MOD << endl;
    }

    return 0;
}