Boring Numbers

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
ll dp[100][2][2][2];
ll solve(string r,int n,bool even,bool leading,bool tight ){
    if(n==0){
        return 1;
    }
    if(dp[n][even][leading][tight]!=-1){
        return dp[n][even][leading][tight];
    }
    if(even){
        int ub=tight?(r[r.length()-n]-'0'):9;

        ll ans=0;
        
        vector<int> digits={0,2,4,6,8};
        for(auto it:digits){
            if(it<=ub)
            ans+=solve(r,n-1,0,0,(tight&(it==ub)));
        }

        return dp[n][even][leading][tight]=ans;
    }
    else{
        int ub=tight?(r[r.length()-n]-'0'):9;
        vector<int> digits={1,3,5,7,9};

        ll ans=0;
        if(leading==1){
            ans+=solve(r,n-1,0,1,0);
        }
        for(auto it:digits){
            if(it<=ub)
            ans+=solve(r,n-1,1,0,(tight&(it==ub)));
        }
        return dp[n][even][leading][tight]=ans;
    }

    
}
int main(){
    ll t;
    cin>>t; ll i=1;
    while(t--){
        ll L,R;
        cin>>L>>R;
        L--;
        cout<<"Case"<<" "<<"#"<<i<<":"<<" ";i++;

        string l=to_string(L);
        string r=to_string(R);
        memset(dp,-1,sizeof dp);
        ll fr=solve(r,r.length(),0,1,1);
        memset(dp,-1,sizeof dp);
        ll fl=solve(l,l.length(),0,1,1);

        cout<<(fr-fl)<<endl;
    }
}