#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define i128 __int128_t const int lim=90; inline i128 trs(i128 S,int c){ i128 T=0; for(int i=0;i<c;i++) if((S>>i)&1) T|=((i128(1))<<(c-i)); T|=S>>c; T|=S<<c; T&=(((i128(1))<<lim+1)-1); // if(c==0)assert(S==T); return T; } map<i128,int>id; i128 num[20034]; int ct=0; inline void dfs(int dep,int rem,i128 S){ if(dep==10){ if(!id.count(S))id[S]=++ct,num[ct]=S; return ; } for(int i=0;i<=rem;i++) dfs(dep+1,rem-i,S),S=trs(S,dep); } int nxt[20030][10]; int f[20030][20][10]; inline int calc(int r,int k){ if(r==0)return 1; if(k>=9)return r+1; int now=1; string s=to_string(r); int p=s.size(); int res=0; for(int i=0;i<p;i++){ int c=s[i]-'0'; int rem=p-i-1; for(int j=0;j<c;j++) res+=f[nxt[now][j]][rem][k];//,cout<<now<<" "<<j<<" "<<nxt[now][j]<<" "<<rem<<" "<<f[nxt[now][j]][rem][k]<<endl; now=nxt[now][c]; } res+=f[now][0][k]; return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("true.in","r",stdin); // freopen("true.out","w",stdout); // int C=clock(); dfs(1,18,1); for(int i=1;i<=ct;i++){ for(int j=0;j<=9;j++){ i128 T=trs(num[i],j); // if(j==0)assert(T==num[i]); if(!id.count(T))nxt[i][j]=i; else nxt[i][j]=id[T]; } int mn=9; for(int j=0;j<=8;j++) if((num[i]>>j)&1){mn=j;break;} for(int j=mn;j<=8;j++) f[i][0][j]=1; } for(int t=1;t<=18;t++){ for(int i=1;i<=ct;i++) for(int j=0;j<=9;j++) for(int k=0;k<=8;k++) f[i][t][k]+=f[nxt[i][j]][t-1][k]; } // cout<<calc(60,5)<<endl; // return 0; // for(int i=1;i<=9;i++) // cout<<calc(i,5)<<" "; // cout<<endl; int q; cin>>q; while(q--){ int l,r,k; cin>>l>>r>>k; cout<<calc(r,k)-calc(l-1,k)<<endl; } // cout<<(clock()-C)*1000/CLOCKS_PER_SEC<<endl; cout.flush(); fflush(stdout); return 0; } /* 7 1 6 159 153 6 114400 6645 107755 1884710 10613 1874097 987371625 123336731 864034894 123123123124 123123 123123000001 7 1 6 159 153 6 114400 6645 107755 1884710 10613 1874097 987360729 123335787 864024942 123123123124 123123 123123000001 */