Find the number of consecutive odd-numbered numbers in the range, and the number of consecutive even-numbered numbers is odd

For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).

Input

First line a t,then t cases.every line contains two integers L and R.

Output

Print the output for each case on one line in the format as shown below.

Sample Input

2    
1 100    
110 220 

Sample Output

Case #1: 29
Case #2: 36

码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
Using namespace std;
Ll dp[20][2][2];//dp[len][pre][e] represents the first digit, whether the previous digit is odd or even, and e indicates whether to add an odd number or the same as pre Even number.
Int a[20];
Ll dfs(int len, int pre, int e,bool flag,bool s)//pre represents the previous number, 0 means even number, 1 means odd number. e=0 does not need to be added. e=1 needs to be added. s record prefix and s=false are all 0s.
{
    If(len<0)
        {
            Return e==1?0:1;
        }
        If(flag==false&&dp[len][pre][e]!=-1&&s)
        {
            Return dp[len][pre][e];
        }
        Ll ans=0;
        Int cnt=flag?a[len]:9;
        For(int i=0;i<=cnt;i++)
        {
            If(s==false)
            {
                If(i==0)
                {
                    Ans+=dfs(len-1,0,0,flag&&i==cnt,false);
                }
                Else
                {
                    Ans+=dfs(len-1,i%2,i%2==1?1:0,flag&&i==cnt,true);
                }
            }
            Else if(i%2==1)
            {
               If(pre%2==1)
               {
                   Ans+=dfs(len-1,1,e^1,flag&&i==cnt,true);
               }
               Else
                {
                    If(e==0)
                    {
                        Ans+= dfs(len-1,1,1,flag&&i==cnt,true);
                    }
                }
            }
            Else
            {
                If(pre%2==0)
                Ans+=dfs(len-1,0,e^1,flag&&i==cnt,true);
                Else
                {
                    If(e==0)
                    {
                        Ans+=dfs(len-1,0,0,flag&&i==cnt,true);
                    }
                }
            }
        }

        If(!flag&&s)
            Dp[len][pre][e]=ans;
        Return ans;
}
Ll solve(ll x)
{
    Int len=0;
     Memset(a,0,sizeof(0));
    While(x>0)
    {
        a[len++]=x%10;
        x/=10;
    }
    Return dfs(len-1,0,0,true,false);
}
Int main()
{
     Int t, ca=1;
        Scanf("%d",&t);
        Memset(dp,-1,sizeof(dp));
        While(t--)
        {
            Long long int l,r;
            Scanf("%I64d%I64d",&l,&r);
            Printf("Case #%d: %I64d\n",ca++,solve(r)-solve(l-1));
        }
        Return 0;
}