//(ᗜ ˰ ᗜ)
// #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];
int l, r, p, len, a[1005];
ll get(ll n)
{
	ll ans = 0;
	while (n)
	{
		ans += n % 10;
		n /= 10;
	}
	return ans;
}
int dfs(int pos, int sum, int limit, int lead)
{
	if (!pos)
	{
		FOR(i, 1, k - 1)
		sum = get(sum);
		return sum == m;
	}
	if (!limit && f[pos][sum] != -1 && !lead)
		return f[pos][sum];
	int res = 0, up = limit ? a[pos] : 9;
	for (int i = 0; i <= up; i++)
	{
		res += dfs(pos - 1, sum + i, limit && i == up, lead && !i);
		res %= MOD;
	}
	return limit ? res : (lead ? res : f[pos][sum] = res);
}
int cal(str n)
{
	memset(f, -1, sizeof f);
	len = 0;
	ROF(i, n.size() - 1, 0)
	a[++len] = n[i] - '0';
	return dfs(len, 0, 1, 1);
}
void Solve(void)
{
	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;
}