//(ᗜ ˰ ᗜ)
// #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 = int;
	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, 4);
	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;
}

answer.code:14:15: error: expected nested-name-specifier before ‘ll’
   14 |         using ll = int;
      |               ^~
answer.code:15:15: error: expected nested-name-specifier before ‘db’
   15 |         using db = double;
      |               ^~
answer.code:27:9: error: ‘constexpr’ does not name a type
   27 |         constexpr long long LNF = 0x3f3f3f3f3f3f3f3fLL;
      |         ^~~~~~~~~
answer.code:27:9: note: C++11 ‘constexpr’ only available with ‘-std=c++11’ or ‘-std=gnu++11’
answer.code:28:9: error: ‘constexpr’ does not name a type
   28 |         constexpr int INF = 0x3f3f3f3f;
      |         ^~~~~~~~~
answer.code:28:9: note: C++11 ‘constexpr’ only available with ‘-std=c++11’ or ‘-std=gnu++11’
answer.code:29:9: error: ‘constexpr’ does not name a type
   29 |         constexpr long long MOD = 1e9 + 7;
      |         ^~~~~~~~~
answer.code:29:9: note: C++11 ‘constexpr’ only available with ‘-std=c++11’ or ‘-std=gnu++11’
answer.code:30:9: error: ‘constexpr’ does not name a type
   30 |         constexpr ll MXN = 1e6 + 5;
      |         ^~~~~~~~~
answer.code:30:9: note: C++11 ‘constexpr’ only available with ‘-std=c++11’ or ‘-std=gnu++11’
answer.code:31:9: error: ‘ll’ does not name a type; did you mean ‘pll’?
   31 |         ll KSM(ll base, ll exp, ll MOD)
      |         ^~
      |         pll
answer.code:47:1: error: ‘ll’ does not name a type; did you mean ‘pll’?
   47 | ll x;
      | ^~
      | pll
answer.code:48:1: error: ‘ll’ does not name a type; did you mean ‘pll’?
   48 | ll k, m;
      | ^~
      | pll
answer.code:49:1: error: ‘ll’ does not name a type; did you mean ‘pll’?
   49 | ll f[1005][9005];
      | ^~
      | pll
answer.code:50:1: error: ‘ll’ does not name a type; did you mean ‘pll’?
   50 | ll l, r, p, len, a[1005];
      | ^~
      | pll
answer.code:51:1: error: ‘ll’ does not name a type; did you mean ‘pll’?
   51 | ll cc(ll n)
      | ^~
      | pll
answer.code: In function ‘int dfs(int, int, int, int)’:
answer.code:65:38: error: ‘k’ was not declared in this scope
   65 |                 for (int i = 1; i <= k - 1; i++)
      |                                      ^
answer.code:67:31: error: ‘cc’ was not declared in this scope
   67 |                         sum = cc(sum);
      |                               ^~
answer.code:69:31: error: ‘m’ was not declared in this scope; did you mean ‘tm’?
   69 |                 return sum == m;
      |                               ^
      |                               tm
answer.code:71:31: error: ‘f’ was not declared in this scope
   71 |         if (!lim && !lead0 && f[pos][sum] != -1)
      |                               ^
answer.code:75:24: error: ‘a’ was not declared in this scope
   75 |         int up = lim ? a[pos] : 9;
      |                        ^
answer.code:80:24: error: ‘MOD’ was not declared in this scope
   80 |                 tmp %= MOD;
      |                        ^~~
answer.code:84:24: error: ‘f’ was not declared in this scope
   84 |                 return f[pos][sum] = tmp;
      |                        ^
answer.code: In function ‘int cal(std::string)’:
answer.code:92:19: error: ‘p’ does not name a type
   92 |         for (auto p : s)
      |                   ^
answer.code:95:10: error: expected ‘;’ before ‘return’
   95 |         }
      |          ^
      |          ;
   96 |         return dfs(len, 0, 1, 1);
      |         ~~~~~~
answer.code:96:9: error: expected primary-expression before ‘return’
   96 |         return dfs(len, 0, 1, 1);
      |         ^~~~~~
answer.code:95:10: error: expected ‘;’ before ‘return’
   95 |         }
      |          ^
      |          ;
   96 |         return dfs(len, 0, 1, 1);
      |         ~~~~~~
answer.code:96:9: error: expected primary-expression before ‘return’
   96 |         return dfs(len, 0, 1, 1);
      |         ^~~~~~
answer.code:95:10: error: expected ‘)’ before ‘return’
   95 |         }
      |          ^
      |          )
   96 |         return dfs(len, 0, 1, 1);
      |         ~~~~~~
answer.code:92:13: note: to match this ‘(’
   92 |         for (auto p : s)
      |             ^
answer.code: In function ‘void Solve()’:
answer.code:102:25: error: ‘f’ was not declared in this scope
  102 |                         f[i][j] = -1;
      |                         ^
answer.code:103:21: error: ‘k’ was not declared in this scope
  103 |         cin >> n >> k >> m;
      |                     ^
answer.code:103:26: error: ‘m’ was not declared in this scope; did you mean ‘tm’?
  103 |         cin >> n >> k >> m;
      |                          ^
      |                          tm
answer.code: In function ‘int main()’:
answer.code:110:46: error: ‘nullptr’ was not declared in this scope
  110 |         ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
      |                                              ^~~~~~~
answer.code: In function ‘int cal(std::string)’:
answer.code:91:16: warning: control reaches end of non-void function [-Wreturn-type]...