#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; typedef __int128 i128; const int maxn=2e5+10,mod=998244353; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int ct,nxt[maxn][10],X[20],dp[114]; ll h[maxn][20][10]; i128 upd(i128 S,int c){ up(i,0,90)dp[i]=0; up(i,0,90){ if(S&1)dp[abs(i-c)]=dp[i+c]=1;S>>=1; }i128 res=0,w=1; up(i,0,90){if(dp[i])res|=w;w<<=1;} return res; } map<i128,int>dis,id; int g(i128 S){ up(i,0,9)if((S>>i)&1)return i; return 114514; } ll f[maxn]; void bfs(){ dis[1]=0;queue<i128>q;q.push(1); id[1]=++ct;f[1]=1; while(!q.empty()){ i128 res=q.front();q.pop(); if(dis[res]==18)break; up(j,0,9){ i128 w=upd(res,j); if(!dis.count(w)){ id[w]=++ct,f[ct]=w; dis[w]=dis[res]+1;q.push(w); }nxt[id[res]][j]=id[w]; } }up(i,1,ct)up(j,0,9)h[i][0][j]=(g(f[i])<=j); up(i,1,18)up(j,1,ct)up(k,0,9)up(w,0,9)h[j][i][k]+=h[nxt[j][w]][i-1][k]; //cout<<"count "<<ct<<endl; } ll cal(ll x,int k){ up(i,1,18)X[i]=x%10,x/=10; reverse(X+1,X+19);//up(i,1,18)printf("%d",X[i]);printf("\n"); ll res=0;int u=1; up(i,0,18){ up(j,0,X[i]-1)res+=h[nxt[u][j]][18-i][k]; u=nxt[u][X[i]]; }res+=h[u][0][k];return res; } void slv(){ bfs();int q=read(); //cout<<"test "<<cal(100,9)<<endl; while(q--){ ll l=read(),r=read(),k=min(read(),9ll); ll res=cal(r,k)-cal(l-1,k); printf("%lld\n",res); } }int main(){ //freopen("true.in","r",stdin); //freopen("true.out","w",stdout); slv(); fclose(stdin); fclose(stdout); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }