Light OJ 1140 / Digit DP

/***
 created: 2022-09-07-23.20.28
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll dp[13][13][2][2];

vector<ll>digit;

ll solve(ll in,ll cnt,bool start, bool f)
{
    if(in==digit.size())
    {
        return cnt;
    }

    if(dp[in][cnt][start][f]!=-1) return dp[in][cnt][start][f];

    ll ans=0;
    ll lim;

    if(f) lim=9;
    else lim=digit[in];

    for(ll i=0; i<=lim; i++)
    {
        ans+=solve(in+1, cnt + (i==0 && start), start || (i!=0), f ||(i<lim));
    }

    return dp[in][cnt][start][f]=ans;
}

ll init(ll b)
{
    digit.clear();
    memset(dp,-1,sizeof dp);
    while(b)
    {
        digit.push_back(b%10);
        b/=10;
    }
    reverse(digit.begin(),digit.end());

    return solve(0,0,0,0);
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m,i,a,b,ans;

        cin>>a>>b;

        init(b);

        ans=solve(0,0,0,0);

        if(a==0) ans++;

        a=max(0ll,a-1);

        init(a);

        ans = ans - solve(0,0,0,0);

        cout<<"Case "<<cs<<": "<<ans<<nl;
    }

    get_lost_idiot;
}