#define _CRT_SECURE_NO_WARNINGS 1
//A
//#include<bits/stdc++.h>
//using namespace std;
//#define ll long long
//#define MAX (int)2e5+100
//vector<int> e[MAX];
//int n;
//
//int dfs(int now, int fa)
//{
//	int cnt = 0;
//	int tot = 0;
//	for (auto it = e[now].begin(); it != e[now].end(); it++) {
//		tot++;
//		if (*it == fa)
//			continue;
//		cnt += dfs(*it, now);
//	}
//	if (tot == 1)
//		return 1;
//	if (cnt >= 2)
//		return 1;
//	//printf("%d\n", now);
//	return 0;
//}
//
//int main()
//{
//	int i, j, k;
//	cin >> n;
//	//if (n == 1) {
//	//	printf("Wasted.\n");
//	//	return 0;
//	//}
//	for (i = 1; i < n; i++) {
//		int u, v;
//		cin >> u >> v;
//		e[u].push_back(v);
//		e[v].push_back(u);
//	}
//	int res = dfs(1, 0);
//	if (!res)
//		printf("Wasted.\n");
//	else {
//		printf("You win, temporarily.\n");
//	}
//	return 0;
//}

//K
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX (int)2e5+100
#define mod 1000000007
int k, m;
string s;
ll dp[1100][9100];//λ\xca\xfd \xca\xfd

bool ju(int x)
{
	for (int i = 0; i < k - 1; i++) {
		int tmp = 0;
		while (x) {
			tmp += x % 10;
			x /= 10;
		}
		x = tmp;
	}
	if (x == m)
		return 1;
	return 0;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int i, j;
	int T;
	cin >> T;
	//for (i = 0; i <= 9; i++)
	//	dp[1][i] = 1;
	//for (i = 2; i <= 1000; i++) {
	//	ll tmp = 0;
	//	for (j = 0; j <= 9 * i; j++) {
	//		if (j > 9) {
	//			tmp -= dp[i - 1][j - 9];
	//		}
	//		tmp += dp[i - 1][j];
	//		tmp %= mod;
	//		dp[i][j] = tmp;
	//		//for (int p = j; p >= 0 && p >= j - 9; p--) {
	//		//	dp[i][j] += dp[i - 1][p];
	//		//	dp[i][j] %= mod;
	//		//}
	//		
	//	}
	//}
	//for (i = 1; i <= 5; i++) {
	//	for (j = 0; j <= 10; j++) {
	//		cout << dp[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	while (T--) {
		cin >> s >> k >> m;
		if (k >= 4)
			k = 4;
		if (m > 9000) {
			printf("0\n");
			continue;
		}
		//for (i = 0; i <= s[s.size() - 1] - '0'; i++)
		//	dp[0][i] = 1;
		ll res = 0;
		int p;
		int sum = 0;
		sum = s[0] - '0';
		memset(dp, 0, sizeof(dp));
		int len = s.size();
		for (i = 0; i < s[0] - '0'; i++)
		{
			dp[1][i] = 1;
		}
		for (i = 2; i <= len; i++)
		{
			ll tmp = 0;
			for (j = 0; j <= 9 * i; j++)
			{
				if (j - sum < s[i - 1] - '0' && j - sum >= 0)
				{
					dp[i][j]++;
				}
				if (j > 9)
					tmp -= dp[i - 1][j - 10];
				tmp += dp[i - 1][j];
				tmp %= mod;
				dp[i][j] += tmp;
			}
			sum += s[i - 1] - '0';
		}
		dp[len][sum]++;
		//for (i = 0; i < s.size(); i++) {
		//	sum += (s[i] - '0');
		//}
		//
		////if (ju(sum))
		////	res++;
		////cout << sum << ' ';
		for (i = 1; i <= 9000; i++) {
			if (ju(i)) {
				res += dp[len][i];
				res %= mod;
				//if (sum - (s[s.size() - 1] - '0') >= i - 9 && sum - (s[s.size() - 1] - '0') <= i)
				//	res++;
				////cout << i << '\n';
				//int ssum = i;
				////res += dp[s.size() - 1][m];
				////cout << res << '\n';
				//for (j = 0; j < s.size(); j++) {
				//	int len = s.size();
				//	for (p = 0; p < s[j] - '0'; p++) {
				//		if (ssum - p < 0)
				//			break;
				//		res += dp[len - 1 - j][ssum - p];
				//		//res--;
				//		//cout << len - 1 - j << ' ' << ssum - p << ' ' << res << '\n';
				//		res %= mod;
				//	}
				//	ssum -= (s[j] - '0');
				//	if (ssum < 0)
				//		break;
				//	//cout << res << '\n';
				//}
			}
		}
		cout << res << '\n';
	}
	return 0;
}