/*
题意：
给你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=;
int len=;
while(num)
{
int temp=num%;
if(curr==)
{
if(temp%)
curr=;
else curr=;
len=;
}
else
{
if(curr==)
{
if(temp%)
len++;
else
{
if(len%)
return false;
len=;
curr=;
}
}
else
{
if(temp%==)
len++;
else
{
if(len%==)
return false;
len=;
curr=;
}
}
}
num/=;
}
if((curr==)&&(len%==))
return true;
if((curr==)&&(len%==))
return true;
return false;
}
int get_wei(unsigned long long t){
int rel=;
while(t>){
rel++;
t/=;
}
return rel;
}
unsigned long long dp[][];
unsigned long long biao[];
void dabiao(){
for(int i=;i<=;i++){
memset(dp,,sizeof(dp));
for(int j=;j<=i;j++){
if(j==){
dp[j][]+=;
dp[j][]+=;
}
dp[j][]+=(dp[j-][]+dp[j-][])*;
dp[j][]+=dp[j-][]*;
dp[j][]+=(dp[j-][]+dp[j-][])*;
dp[j][]+=dp[j-][]*;
}
biao[i]=dp[i][]+dp[i][];
}
}
int fenjie[];
unsigned long long dayudengyu(unsigned long long l){
unsigned long long rel=;
unsigned long long ll=l;
int num=;
while(ll>){
fenjie[num++]=ll%;
ll/=;
}
for(int i=;i<num/;i++){
swap(fenjie[i],fenjie[num-i-]);
}
memset(dp,,sizeof(dp));
for(int i=;i<num;i++){
for(int j=i;j<num;j++){
if(j==i){
if(fenjie[i]&){
if(j==){
dp[j][]=dp[j][]=(-fenjie[i])/;
}
else{
int ttt=(-fenjie[i])/;
dp[j][]=(dp[j-][]+dp[j-][])*ttt;
dp[j][]=dp[j-][]*ttt;
dp[j][]=(dp[j-][]+dp[j-][])*ttt;
dp[j][]=dp[j-][]*ttt;
}
}
else{
if(j==){
dp[j][]=(-fenjie[i])/-;
dp[j][]=(-fenjie[i])/;
}
else{
int ttt=(-fenjie[i])/;
dp[j][]=(dp[j-][]+dp[j-][])*(ttt-);
dp[j][]=dp[j-][]*(ttt-);
dp[j][]=(dp[j-][]+dp[j-][])*ttt;
dp[j][]=dp[j-][]*ttt;
}
}
}
else{
dp[j][]=(dp[j-][]+dp[j-][])*;
dp[j][]=dp[j-][]*;
dp[j][]=(dp[j-][]+dp[j-][])*;
dp[j][]=dp[j-][]*;
}
}
rel+=dp[num-][]+dp[num-][];
memset(dp,,sizeof(dp));
for(int j=;j<=i;j++){
if(j==){
if(fenjie[j]&)dp[j][]=;
else dp[j][]=;
}
else{
if(fenjie[j]&){
dp[j][]=(dp[j-][]+dp[j-][]);
dp[j][]=dp[j-][];
}
else{
dp[j][]=(dp[j-][]+dp[j-][]);
dp[j][]=dp[j-][];
}
}
}
}
return rel+dp[num-][]+dp[num-][];
}
unsigned long long xiaoyudengyu(unsigned long long l){
unsigned long long rel=;
unsigned long long ll=l;
int num=;
while(ll>){
fenjie[num++]=ll%;
ll/=;
}
for(int i=;i<num/;i++){
swap(fenjie[i],fenjie[num-i-]);
}
memset(dp,,sizeof(dp));
for(int i=;i<num;i++){
for(int j=i;j<num;j++){
if(j==i){
if(fenjie[i]&){
if(j==){
dp[j][]=fenjie[i]/;
dp[j][]=fenjie[i]/;
}
else{
unsigned long long ttt=(fenjie[i])/+;
unsigned long long tt=fenjie[i]/;
dp[j][]=(dp[j-][]+dp[j-][])*ttt;
dp[j][]=dp[j-][]*ttt;
dp[j][]=(dp[j-][]+dp[j-][])*tt;
dp[j][]=dp[j-][]*tt;
}
}
else{
if(j==){
dp[j][]=max(fenjie[i]/-,);
dp[j][]=(fenjie[i])/;
}
else{
int ttt=max(,fenjie[i]/);
int tt=fenjie[i]/;
dp[j][]=(dp[j-][]+dp[j-][])*(ttt);
dp[j][]=dp[j-][]*(ttt);
dp[j][]=(dp[j-][]+dp[j-][])*(tt);
dp[j][]=dp[j-][]*tt;
}
}
}
else{
dp[j][]=(dp[j-][]+dp[j-][])*;
dp[j][]=dp[j-][]*;
dp[j][]=(dp[j-][]+dp[j-][])*;
dp[j][]=dp[j-][]*;
}
}
rel+=dp[num-][]+dp[num-][];
//cout << rel << endl;
memset(dp,,sizeof(dp));
for(int j=;j<=i;j++){
if(j==){
if(fenjie[j]&)dp[j][]=;
else dp[j][]=;
}
else{
if(fenjie[j]&){
dp[j][]=(dp[j-][]+dp[j-][]);
dp[j][]=dp[j-][];
}
else{
dp[j][]=(dp[j-][]+dp[j-][]);
dp[j][]=dp[j-][];
}
}
}
}
return rel+dp[num-][]+dp[num-][];
}
int main(){
int a;
dabiao();
int cas=;
scanf("%d",&a); while(a--){
cas++;
unsigned long long l,r,ll,rr;
unsigned long long rel=;
scanf("%llu%llu",&l,&r);
int st=get_wei(l);
int ed=get_wei(r);
for(int i=st+;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);
} }