//(ᗜ ˰ ᗜ)
// #define NDEBUG
#include <bits/stdc++.h>
using namespace std;
namespace LING
{
#ifdef ONLINE_JUDGE
#define DBG(...) ;
#define dbg(...) ;
#else
#define DBG(x) cout << "! " << #x << " = " << x << endl
#include "debug.h"
#endif
	using ll = long long;
	using db = double;
#define SPO(x) fixed << setprecision(x)
#define FOR(i, l, r) for (ll i = l; i <= (r); ++i)
#define ROF(i, r, l) for (ll i = r; i >= (l); --i)
#define edl '\n'
#define fir first
#define sec second
#define str string
#define pll pair<ll, ll>
#define heap priority_queue
	// constexpr db PI = acos(-1.0);
	// constexpr db EPS = 1.0e-9;
	constexpr long long LNF = 0x3f3f3f3f3f3f3f3fLL;
	constexpr int INF = 0x3f3f3f3f;
	constexpr long long MOD = 1e9 + 7;
	constexpr ll MXN = 1e6 + 5;
	ll KSM(ll base, ll exp, ll MOD)
	{
		ll res = 1;
		base %= MOD;
		while (exp)
		{
			if (exp & 1)
				res = (res * base) % MOD;
			base = (base * base) % MOD;
			exp >>= 1;
		}
		return res;
	}
}
using namespace LING;
str n;
ll x;
ll k, m;
ll f[1005][9005];
ll l, r, p, len, a[1005];
ll cc(ll n)
{
	ll ans = 0;
	while (n)
	{
		ans += n % 10;
		n /= 10;
	}
	return ans;
}
int dfs(int pos, int sum, int lim, int lead0)
{
	if (pos == 0)
	{
		for (int i = 1; i <= k - 1; i++)
		{
			sum = cc(sum);
		}
		return sum == m;
	}
	if (!lim && !lead0 && f[pos][sum] != -1)
	{
		return f[pos][sum];
	}
	int up = lim ? a[pos] : 9;
	int tmp = 0;
	for (int i = 0; i <= up; i++)
	{
		tmp += dfs(pos - 1, sum + i, lim && (i == up), lead0 && (i == 0));
		tmp %= MOD;
	}
	if (!lim && !lead0)
	{
		return f[pos][sum] = tmp;
	}
	return tmp;
}
int cal(string s)
{
	int len = 0;
	reverse(s.begin(), s.end());
	for (auto p : s)
	{
		a[++len] = p - '0';
	}
	return dfs(len, 0, 1, 1);
}
void Solve(void)
{
	for (int i = 0; i <= 1002; i++)
		for (int j = 0; j <= 9001; j++)
			f[i][j] = -1;
	cin >> n >> k >> m;
	k = min(k, 4LL);
	cout << cal(n) << edl;
	return;
}
int main(void)
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	// #ifndef ONLINE_JUDGE
	// freopen("cin.txt","r",stdin);
	// freopen("cout.txt","w",stdout);
	// #endif

	int t = 1;
	cin >> t;
	while (t--)
		Solve();
	return 0;
}