/*题意：给你l和r，范围9e18，求l到r闭区间有多少个数字满足，连续的奇数的个数都为偶数，连续的偶数的个数都为奇数。例如33433符合要求，44不符合要求。不能含有前导零。思路：队友说是数位dp...我都反映不过来。知道是数位dp以后，思路就显而易见了。dp的方法是最后一位的性质，是偶数还是奇数，是连续的第偶数个还是第奇数个。所以一共只有四种状态，而题目中最多19位数字...用了以上的方法，我们可以轻易解决有n为数字的符合要求的数字的个数。问题是如何考虑边界条件。所以我们可以先判断l和r有多少位。然后提前打表，中间的位数直接加到答案上来就好。现在我们讨论跟l和r位数相同的在l到r范围内的，即大于等于l，小于等于r的个数。假如l和r位数相同，那么我们可以用小于等于r的减去小于等于l的，然后特判l是不是。位数不同，可以直接求和l位数相同的，大于等于l的加上和r位数相同的小于等于r的。所以现在问题转化为，位数确定的情况下，小于等于或者大于等于某个数的符合条件数的个数有多少。类似dfs，依次讨论前几位大于等于某位或者小于等于某位有多少个...（这个大概是数位dp的核心？）【简单说一下，第i次统计的数目是，假如第i位大于边界值，而前i-1位等于边界值的符合要求的数字的数目，这样一直统计到i+1...】*/#include<bits/stdc++.h>using namespace std;bool panduan(unsigned long long num){    int curr=0;    int len=0;    while(num)    {        int temp=num%10;        if(curr==0)        {            if(temp%2)                curr=1;            else curr=2;            len=1;        }        else        {            if(curr==1)            {                if(temp%2)                    len++;                else                {                    if(len%2)                        return false;                    len=1;                    curr=2;                }            }            else            {                if(temp%2==0)                    len++;                else                {                    if(len%2==0)                        return false;                    len=1;                    curr=1;                }            }        }        num/=10;    }    if((curr==1)&&(len%2==0))        return true;    if((curr==2)&&(len%2==1))        return true;    return false;}int get_wei(unsigned long long t){    int rel=0;    while(t>0){        rel++;        t/=10;    }    return rel;}unsigned long long dp[20][4];unsigned long long biao[30];void dabiao(){    for(int i=1;i<=19;i++){        memset(dp,0,sizeof(dp));        for(int j=1;j<=i;j++){            if(j==1){                dp[j][0]+=4;                dp[j][2]+=5;            }            dp[j][0]+=(dp[j-1][1]+dp[j-1][3])*5;            dp[j][1]+=dp[j-1][0]*5;            dp[j][2]+=(dp[j-1][0]+dp[j-1][3])*5;            dp[j][3]+=dp[j-1][2]*5;        }        biao[i]=dp[i][0]+dp[i][3];    }}int fenjie[30];unsigned long long dayudengyu(unsigned long long l){    unsigned long long rel=0;    unsigned long long ll=l;    int num=0;    while(ll>0){        fenjie[num++]=ll%10;        ll/=10;    }    for(int i=0;i<num/2;i++){        swap(fenjie[i],fenjie[num-i-1]);    }    memset(dp,0,sizeof(dp));    for(int i=0;i<num;i++){        for(int j=i;j<num;j++){            if(j==i){                if(fenjie[i]&1){                    if(j==0){                        dp[j][0]=dp[j][2]=(10-fenjie[i])/2;                    }                    else{                        int ttt=(10-fenjie[i])/2;                        dp[j][0]=(dp[j-1][1]+dp[j-1][3])*ttt;                        dp[j][1]=dp[j-1][0]*ttt;                        dp[j][2]=(dp[j-1][0]+dp[j-1][3])*ttt;                        dp[j][3]=dp[j-1][2]*ttt;                    }                }                else{                    if(j==0){                        dp[j][0]=(10-fenjie[i])/2-1;                        dp[j][2]=(10-fenjie[i])/2;                    }                    else{                        int ttt=(10-fenjie[i])/2;                        dp[j][0]=(dp[j-1][1]+dp[j-1][3])*(ttt-1);                        dp[j][1]=dp[j-1][0]*(ttt-1);                        dp[j][2]=(dp[j-1][0]+dp[j-1][3])*ttt;                        dp[j][3]=dp[j-1][2]*ttt;                    }                }            }            else{                dp[j][0]=(dp[j-1][1]+dp[j-1][3])*5;                dp[j][1]=dp[j-1][0]*5;                dp[j][2]=(dp[j-1][0]+dp[j-1][3])*5;                dp[j][3]=dp[j-1][2]*5;            }        }        rel+=dp[num-1][0]+dp[num-1][3];        memset(dp,0,sizeof(dp));        for(int j=0;j<=i;j++){            if(j==0){                if(fenjie[j]&1)dp[j][2]=1;                else dp[j][0]=1;            }            else{                if(fenjie[j]&1){                    dp[j][2]=(dp[j-1][0]+dp[j-1][3]);                    dp[j][3]=dp[j-1][2];                }                else{                    dp[j][0]=(dp[j-1][1]+dp[j-1][3]);                    dp[j][1]=dp[j-1][0];                }            }        }    }    return rel+dp[num-1][0]+dp[num-1][3];}unsigned long long xiaoyudengyu(unsigned long long l){    unsigned long long rel=0;    unsigned long long ll=l;    int num=0;    while(ll>0){        fenjie[num++]=ll%10;        ll/=10;    }    for(int i=0;i<num/2;i++){        swap(fenjie[i],fenjie[num-i-1]);    }    memset(dp,0,sizeof(dp));    for(int i=0;i<num;i++){        for(int j=i;j<num;j++){            if(j==i){                if(fenjie[i]&1){                    if(j==0){                        dp[j][0]=fenjie[i]/2;                        dp[j][2]=fenjie[i]/2;                    }                    else{                        unsigned long long ttt=(fenjie[i])/2+1;                        unsigned long long tt=fenjie[i]/2;                        dp[j][0]=(dp[j-1][1]+dp[j-1][3])*ttt;                        dp[j][1]=dp[j-1][0]*ttt;                        dp[j][2]=(dp[j-1][0]+dp[j-1][3])*tt;                        dp[j][3]=dp[j-1][2]*tt;                    }                }                else{                    if(j==0){                        dp[j][0]=max(fenjie[i]/2-1,0);                        dp[j][2]=(fenjie[i])/2;                    }                    else{                        int ttt=max(0,fenjie[i]/2);                        int tt=fenjie[i]/2;                        dp[j][0]=(dp[j-1][1]+dp[j-1][3])*(ttt);                        dp[j][1]=dp[j-1][0]*(ttt);                        dp[j][2]=(dp[j-1][0]+dp[j-1][3])*(tt);                        dp[j][3]=dp[j-1][2]*tt;                    }                }            }            else{                dp[j][0]=(dp[j-1][1]+dp[j-1][3])*5;                dp[j][1]=dp[j-1][0]*5;                dp[j][2]=(dp[j-1][0]+dp[j-1][3])*5;                dp[j][3]=dp[j-1][2]*5;            }        }        rel+=dp[num-1][0]+dp[num-1][3];        //cout << rel << endl;        memset(dp,0,sizeof(dp));        for(int j=0;j<=i;j++){            if(j==0){                if(fenjie[j]&1)dp[j][2]=1;                else dp[j][0]=1;            }            else{                if(fenjie[j]&1){                    dp[j][2]=(dp[j-1][0]+dp[j-1][3]);                    dp[j][3]=dp[j-1][2];                }                else{                    dp[j][0]=(dp[j-1][1]+dp[j-1][3]);                    dp[j][1]=dp[j-1][0];                }            }        }    }    return rel+dp[num-1][0]+dp[num-1][3];}int main(){    int a;    dabiao();    int cas=0;    scanf("%d",&a);    while(a--){        cas++;        unsigned long long l,r,ll,rr;        unsigned long long rel=0;        scanf("%llu%llu",&l,&r);        int st=get_wei(l);        int ed=get_wei(r);        for(int i=st+1;i<ed;i++){            rel+=biao[i];        }        if(st==ed){            rel+=xiaoyudengyu(r);            rel+=panduan(l);            rel-=xiaoyudengyu(l);        }        else{            rel+=dayudengyu(l);            rel+=xiaoyudengyu(r);        }        printf("Case #%d: ",cas);        printf("%llu\n",rel);    }}