1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7  8 typedef long long LL; 9 const int maxn = 1e5+5;10 LL dp[20][10][2],f[20][10][2],e[20][10][2];11 int d[65];12 13 LL dfs(int pos,int pre,int zero,int limit){14     if(pos == 0) return 1;15     if(!limit && ~dp[pos][pre][zero]) return dp[pos][pre][zero];16     int top = limit?d[pos]:9;17     LL res = 0LL;18     for(int i = 0;i <= top;i++){19         if(zero == 1){20             if(i == 0) res += dfs(pos-1,0,1,limit && i == top);21             else res += dfs(pos-1,i,0,limit && i == top);22         }23         else{24             if(i >= pre) res += dfs(pos-1,i,0,limit && i == top);25         }26     }27     if(!limit) dp[pos][pre][zero] = res;28     return res;29 }30 31 LL Dfs(int pos,int pre,int zero,int limit){32     if(pos == 0) return 1;33     if(!limit && ~f[pos][pre][zero]) return f[pos][pre][zero];34     int top = limit?d[pos]:9;35     LL res = 0LL;36     for(int i = 0;i <= top;i++){37         if(zero == 1){38             if(i == 0) res += Dfs(pos-1,0,1,limit && i == top);39             else res += Dfs(pos-1,i,0,limit && i == top);40         }41         else{42             if(i <= pre) res += Dfs(pos-1,i,0,limit && i == top);43         }44     }45     if(!limit) f[pos][pre][zero] = res;46     return res;47 }48 49 LL DFS(int pos,int pre,int zero,int limit){50     if(pos == 0) return 1;51     if(!limit && ~e[pos][pre][zero]) return e[pos][pre][zero];52     int top = limit?d[pos]:9;53     LL res = 0LL;54     for(int i = 0;i <= top;i++){55         if(zero == 1){56             if(i == 0) res += DFS(pos-1,0,1,limit && i == top);57             else res += DFS(pos-1,i,0,limit && i == top);58         }59         else{60             if(i == pre) res += DFS(pos-1,i,0,limit && i == top);61         }62     }63     if(!limit) e[pos][pre][zero] = res;64     return res;65 }66 67 LL solve(LL x){68     int len = 0;69     //printf("x = %lld ",x);70     71      while(x){72         d[++len] = x%10;73         x = x/10;74     }75     LL l = dfs(len,0,1,1);76     LL r = Dfs(len,0,1,1);77     LL cnt = DFS(len,0,1,1);78     LL res = l+r - cnt;79    // printf("l = %lld r = %lld cnt = %lld res = %lld \n",l,r,cnt,res);80     return res;81 }82 83 int main(){84     int T;85     memset(e,-1,sizeof(e));86     memset(dp,-1,sizeof(dp));87     memset(f,-1,sizeof(f));88     LL tmp = DFS(18,0,1,1);89     LL l = dfs(18,0,1,1);90     LL r = Dfs(18,0,1,1);91     scanf("%d",&T);92     while(T--){93         LL L,R;94         scanf("%lld %lld",&L,&R);95         LL ans = solve(R) - solve(L-1);96         printf("%lld\n",ans);97     }98     return 0;99 }