#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=1e4+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
template <int m>
struct static_modint
{
	using mint=static_modint;

public:
	static_modint() : v(0) {}
	template <class T>
	static_modint(T x)
	{
		x=(x%(ll)(umod()));
		if(x<0)x+=umod();
		v=(unsigned int)(x);
	}

	static_modint(bool x) { v=((unsigned int)(x)%umod()); }

	unsigned int val() const { return v; }

	mint &operator++()
	{
		v++;
		if(v==umod()) v=0;
		return *this;
	}

	mint &operator--()
	{
		if(v==0) v=umod();
		v--;
		return *this;
	}

	mint operator++(int)
	{
		mint result=*this;
		++*this;
		return result;
	}

	mint operator--(int)
	{
		mint result=*this;
		--*this;
		return result;
	}

	mint &operator+=(const mint &rs)
	{
		v+=rs.v;
		if(v>=umod()) v-=umod();
		return *this;
	}

	mint &operator-=(const mint &rs)
	{
		if(v<rs.v) v+=umod();
		v-=rs.v;
		return *this;
	}

	mint &operator*=(const mint &rs)
	{
		ull z=v;
		z*=rs.v;
		v=(unsigned int)(z%umod());
		return *this;
	}

	mint &operator/=(const mint &rs) { return *this=*this*rs.inv(); }

	mint operator+() const { return *this; }
	mint operator-() const { return mint()-*this; }

	mint pow(ll n) const
	{
		assert(n>=0);
		mint x=*this, r=1;
		while(n)
		{
			if(n&1) r*=x;
			x*=x;
			n>>=1;
		}
		return r;
	}

	mint inv() const
	{
		//assert(v);
		return pow(umod()-2);
	}

	istream &operator>>(istream &in)
	{
		in>>v;
		*this=static_modint(v);
		return in;
	}

	ostream &operator<<(ostream &o)const
	{
		o<<v;
		return o;
	}

	friend mint operator+(const mint &l, const mint &r)
	{
		return mint(l)+=r;
	}

	friend mint operator-(const mint &l, const mint &r)
	{
		return mint(l)-=r;
	}

	friend mint operator*(const mint &l, const mint &r)
	{
		return mint(l)*=r;
	}

	friend mint operator/(const mint &l, const mint &r)
	{
		return mint(l)/=r;
	}

	friend bool operator==(const mint &l, const mint &r)
	{
		return l.v==r.v;
	}

	friend bool operator!=(const mint &l, const mint &r)
	{
		return l.v!=r.v;
	}

	friend bool operator<(const mint &l, const mint &r)
	{
		return l.v<r.v;
	}

	friend bool operator>(const mint &l, const mint &r)
	{
		return l.v>r.v;
	}

	friend bool operator<=(const mint &l, const mint &r)
	{
		return l.v<=r.v;
	}

	friend bool operator>=(const mint &l, const mint &r)
	{
		return l.v>=r.v;
	}

	friend ostream &operator<<(ostream &o, mint u)
	{
		u.operator<<(o);
		return o;
	}

	friend istream &operator>>(istream &in, mint &u)
	{
		u.operator>>(in);
		return in;
	}

private:
	unsigned int v;
	static constexpr unsigned int umod() { return m; }
};
typedef static_modint<mod> mint;

int val[maxn][6];
void init(const int n=9000)
{
	auto f=[](int x)->int
	{
		string s=to_string(x);
		int ans=0;
		for(char c:s)
		{
			ans+=c-'0';
		}
		return ans;
	};
	for(int i=1; i<=n; i++)
		val[i][0]=i;
	for(int i=1; i<=n; i++)
	{
		for(int k=1; k<=5; k++)
		{
			val[i][k]=f(val[i][k-1]);
		}
	}
}
string N;
int k, m;
int timestamp=0;
int vis[1005][9005];
mint f[1005][9005];
const int LIMIT_TAR[]={0, 9000, 35, 11, 9, 9};
mint dfs(int pos, bool limited, bool leading_zero, int sum)
{
	if(sum>m)return 0;
	if(pos==0)
	{
		return val[sum][k-1]==m;
	}
	if(!limited&&!leading_zero&&vis[pos][sum]==timestamp)return f[pos][sum];
	mint ans=0;
	int lim=limited?N[N.size()-pos]-'0':9;
	for(int i=0; i<=lim; i++)
	{
		ans+=dfs(pos-1, limited&&i==lim, leading_zero&&!i, sum+i);
	}
	if(!limited&&!leading_zero)
	{
		vis[pos][sum]=timestamp;
		return f[pos][sum]=ans;
	}
	return ans;
}
mint calc()
{
	timestamp++;
	return dfs(N.size(), true, true, 0);
}
mint getans()
{
	_min(k, 4);
	return calc();
}
int main()//MARK: main
{
#ifndef xxx
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
	cout<<fixed<<setprecision(10);
	init();
	int t;
	cin>>t;
	while(t--)
	{
		cin>>N>>k>>m;
		cout<<getans()<<'\n';
	}
	return 0;
}