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

using namespace std;

const int MOD = 1'000'000'007;

// 计算数字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;
}

answer.code:7:18: warning: multi-character character constant [-Wmultichar]
    7 | const int MOD = 1'000'000'007;
      |                  ^~~~~
answer.code:7:26: warning: missing terminating ' character
    7 | const int MOD = 1'000'000'007;
      |                          ^
answer.code:7:26: error: missing terminating ' character
    7 | const int MOD = 1'000'000'007;
      |                          ^~~~~
answer.code:7:18: error: expected ‘,’ or ‘;’ before '\x303030'
    7 | const int MOD = 1'000'000'007;
      |                  ^~~~~
answer.code: In function ‘int g(int, int)’:
answer.code:22:13: error: ‘digitSum’ was not declared in this scope
   22 |         n = digitSum(n);
      |             ^~~~~~~~