A palindromic number or numeral palindrome is a 'symmetrical' number like 16461 that remains the same when its digits are reversed. In this problem you will be given two integers i j, you have to find the number of palindromic numbers between i and j (inclusive).

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing two integers i j (0 ≤ i, j ≤ 10¹⁷).

Output

For each case, print the case number and the total number of palindromic numbers between i and j (inclusive).

题目大意为：a-b区间有多少个数是回文数，a,b的范围 为10^17

因此只能用数位DP

用DP[pos][len] 记录答案 pos表示的是当前的位置，len为回文数长度

用num[pos] 记录前mid位的信息

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; typedef long long ll; ll a,b; vector
       
         digit; int num[20]; ll dp[19][19]; ll dfs(int pos,int len,int zero,int done){ if(pos==-1) return 1; if(!done && !zero && ~dp[pos][len]) return dp[pos][len]; ll res = 0; int end = done digit[pos]:9; for(int i = 0; i <= end; i++){ if(zero){ num[len] = i; res += dfs(pos-1,len-!i,zero&&i==0,done&&i==end); }else{ int mid = (len+1)>>1; if(len&1){ if(pos < mid){ if(num[2*mid-pos-1]==i) res += dfs(pos-1,len,zero&&i==0,done&&i==end); }else{ num[pos] = i; res += dfs(pos-1,len,zero&&i==0,done&&i==end); } }else{ if(pos == mid){ res += dfs(pos-1,len,zero&&i==0,done&&i==end); }else if(pos < mid){ if(num[mid*2-pos]==i) res += dfs(pos-1,len,zero&&i==0,done&&i==end); } else{ num[pos] = i; res += dfs(pos-1,len,zero&&i==0,done&&i==end); } } } } if(!done && !zero) dp[pos][len] = res; return res; } ll solve(ll x){ digit.clear(); memset(dp,-1,sizeof dp); if(x==0) digit.push_back(0); while(x){ digit.push_back(x%10); x /= 10; } return dfs(digit.size()-1,digit.size()-1,1,1); } int main(){ int ncase,T=1; cin >> ncase; while(ncase--){ cin >> a >> b; if(a > b) swap(a,b); printf("Case %d: %lld\n",T++,solve(b)-solve(a-1)); //cout<<<