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).

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

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

2
1 100
110 220

Case #1: 29
Case #2: 36

2016 ACM/ICPC Asia Regional Shenyang Online

题意：给出一段区间，求其中符合条件：【所有连续的奇数位(那一位的数字是奇数，而不是那一位的序号为奇数)的长度要是偶数，所有连续的偶数位的长度要是奇数】的数的个数。2,4,6,8这种满足条件；11也满足条件。
思路：难。一开始想三维，就是不行。参考了一下要这样开：LL dp[20][2][20][2];//第i位，上一位奇偶，连续位数，当前数是否有前导零

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 150 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..//
int dig[20], len;
LL dp[20][2][20][2];//第i位，上一位奇偶，连续位数，前导零

LL dfs(int pos, int pre = 0, int ln = 0, bool inf = 1, bool ze = 1)//pre 1为奇，0为偶
{
	if (!pos)//处理完最后一位
	{
		if (pre)//最后一位是奇数,如果连续位数为偶数,则可行
			return (ln & 1) == 0;
		//最后一位是偶数,如果连续位数为奇数,则可行
		else return ln & 1;
	}
	//已经搜索过
	if (!inf&&dp[pos][pre][ln][ze] != -1)return dp[pos][pre][ln][ze];
	int en = inf ? dig[pos] : 9;//如果前面的位数小于dig[pos]，inf就会为0，后面的数字可以任取
	LL ans = 0;
	for (int i = 0; i <= en;i++)
	{
		if (i & 1)//奇数
		{
			if (ze)//有前导零
			{
				//如果还是放0,还是有前导零
				if (!i)ans += dfs(pos - 1, 0, 0, inf&&i == en, 1);
				//如果放非0,而且是奇数,连续位数为1,没有前导零
				else ans += dfs(pos - 1, 1, 1, inf&&i == en, 0);
			}
			else if (!pre)//上一位是偶数
			{
				//连续位数为奇数的情况下满足条件
				if (ln & 1)ans += dfs(pos - 1, 1, 1, inf&&i == en, ze);
			}
			//上一位是奇数
			else ans += dfs(pos - 1, 1, ln + 1, inf&&i == en, ze);
		}
		else//偶数
		{
			if (ze)//有前导零
			{
				//如果还是放0,还是有前导零
				if (!i)ans += dfs(pos - 1, 0, 0, inf&&i == en, 1);
				//如果放非0,而且是偶数,连续位数为1,没有前导零
				else ans += dfs(pos - 1, 0, 1, inf&&i == en, 0);
			}
			//上一位是偶数
			else if (!pre)ans += dfs(pos - 1, 0, ln + 1, inf&&i == en, ze);
			else
			{
				//上一位是奇数,连续位数为偶数时满足条件
				if (!(ln & 1))ans += dfs(pos - 1, 0, 1, inf&&i == en, ze);
			}
		}
	}
	if (!inf)dp[pos][pre][ln][ze] = ans;//记录
	return ans;
}
int main()
{
	int T, cas = 1;
	LL l, r;
	cin >> T;
	while (T--)
	{
		memset(dp, -1, sizeof(dp));
		scanf("%lld%lld", &l, &r), l--;
		for (len = 0; l; l /= 10)dig[++len] = l % 10;
		LL tp = dfs(len);
		for (len = 0; r; r /= 10)dig[++len] = r % 10;
		printf("Case #%d: %lld\n", cas++, dfs(len) - tp);
	}
	return 0;
}