#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define i128 __int128_t #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second 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[40034]; int ct=0; inline void init(){ ct=1; num[1]=1; id[1]=1; queue<pii>q; q.push({1,0}); while(!q.empty()){ i128 S=num[p1(q.front())]; int len=p2(q.front()); q.pop(); if(len==18)continue; for(int c=1;c<=9;c++){ i128 T=trs(S,c); if(id.count(T))continue; id[T]=++ct,num[ct]=T; q.push({ct,len+1}); } } } int nxt[40030][10]; int f[40030][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); init(); cout<<ct<<endl; // cout<<ct<<endl; 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)<<" "; cout<<calc(r,k)-calc(l-1,k)<<endl; } // cout<<(clock()-C)*1000/CLOCKS_PER_SEC<<endl; cout.flush(); fflush(stdout); return 0; } /* 9999928787571 974130 9999927813441 9999928800815 974130 9999927826685 */