2.cpp

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i < n; i++)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))
#define PI 3.1415926535897932385
#define uint64 unsigned long long
#define Int long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define ff first
#define ss second
#define bit(n) (1<<(n))
#define Last(i) ( (i) & (-i) )
#define sq(x) ((x) * (x))
#define INF INT_MAX
#define mp make_pair
 
Int na , nb ;
Int dp[ 10 ][ 3 ][ 100 ][ 100 ] ;
 
void  calc( Int a , Int b )
 {
    while( a ) {  a= a/10 ; na++  ; }
    while( b ) {  b= b/10 ; nb++  ; }
 
 }
 
int cnt = 0 ;
Int check(  Int idx , Int even_sum , Int odd_sum )
 {
    if(  (idx&1LL) == 0 )swap( even_sum , odd_sum ) ;
    if(  even_sum - odd_sum != 1 )return  0 ;
    //cout<<even_sum<<" "<<odd_sum<<endl;
    return  1  ;
 }
Int solve(  string& a , Int idx , Int limit , Int small , Int even_sum , Int odd_sum   )
{
   if(  idx   == limit-1 && small == 2 )
              return 0 ;
 
   if(  idx   >=  limit  )
        return 0 ;
 
   if(  dp[idx][small][even_sum][odd_sum] != -1 )return dp[idx][small][even_sum][odd_sum] ;
 
 
 
   Int loop = 9  ;
   Int num = a[idx] - '0' ;
 
   Int sum = 0 ;
 
   Int i = 0 ;
   if(  idx == 0 )i = 1 ;
 
 
   for( ; i <=  loop ; i ++ )
     {
       Int odd = 0, even = 0 ;
       if(  idx&1 )odd += i ;
       else even += i ;
       Int tpeven =  even + even_sum ;
       Int tpodd  =  odd + odd_sum ;
 
      if( small == 0 ) { sum =  sum +  check(idx, tpeven ,tpodd ) +  solve(  a ,  idx + 1 , limit , 0 , tpeven  , tpodd  ) ; }
      if( small == 2 ) { sum =  sum +  check(idx, tpeven ,tpodd )  + solve(  a ,  idx + 1 , limit , 2 , tpeven  , tpodd  ) ; }
      if( small == 1 ) { if(  i > num && idx != limit-1 ) sum =  sum +  check(idx,tpeven ,tpodd )  + solve(  a , idx + 1 , limit , 2 , tpeven , tpodd  ) ;
                         if(  i < num  ) sum =  sum  + check(idx,tpeven ,tpodd )  +  solve(  a , idx + 1 , limit , 0 , tpeven , tpodd) ;
                         if(  i == num ) sum =  sum  + check(idx,tpeven ,tpodd)  +  solve(  a   , idx + 1 , limit , 1 , tpeven , tpodd) ;
                        }
 
     }
 
   dp[ idx ][ small ][even_sum][odd_sum] =  sum ;
   return dp[ idx ][ small ][even_sum][odd_sum] ;
 
}
 
 
int main ( )
{
 
  int t  ;
  scanf("%d",&t) ;
  while(  t-- )
   {
 
        na = nb = 0  ;
        Int a , b ;
        scanf("%lld%lld",&a,&b);
 
 
        calc( a - 1, b );
 
       string bs =  to_string( b ) ;
       string as =  to_string( a -1 ) ;
       Int g ,s ;
 
        memset(dp,-1,sizeof(dp)) ;
        g = solve( bs  ,  0 , nb ,1, 0 ,0  )  ;
 
       memset(dp,-1,sizeof(dp)) ;
        s = solve (  as , 0, na,1 , 0 , 0 );
 
        cout<<g-s<<endl;
 
   }
}