1 #include <bits/stdc++.h>  2 using namespace std;  3 #define fr first  4 #define sc second  5 #define cl clear  6 #define BUG puts("here!!!")  7 #define W(a) while(a--)  8 #define pb(a) push_back(a)  9 #define Rint(a) scanf("%d", &a) 10 #define Rll(a) scanf("%I64d", &a) 11 #define Rs(a) scanf("%s", a) 12 #define Cin(a) cin >> a 13 #define FRead() freopen("in", "r", stdin) 14 #define FWrite() freopen("out", "w", stdout) 15 #define Rep(i, len) for(int i = 0; i < (len); i++) 16 #define For(i, a, len) for(int i = (a); i < (len); i++) 17 #define Cls(a) memset((a), 0, sizeof(a)) 18 #define Clr(a, x) memset((a), (x), sizeof(a)) 19 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 20 #define lrt rt << 1 21 #define rrt rt << 1 | 1 22 #define pi 3.14159265359 23 #define RT return 24 #define lowbit(x) x & (-x) 25 #define onecnt(x) __builtin_popcount(x) 26 typedef long long LL; 27 typedef long double LD; 28 typedef unsigned long long ULL; 29 typedef pair<int, int> pii; 30 typedef pair<string, int> psi; 31 typedef pair<LL, LL> pll; 32 typedef map<string, int> msi; 33 typedef vector<int> vi; 34 typedef vector<LL> vl; 35 typedef vector<vl> vvl; 36 typedef vector<bool> vb; 37  38 const int maxn = 19; 39 int digit[maxn]; 40 LL l, r; 41 LL dp[maxn][2][2][2]; 42  43 LL dfs(int l, int pre, int con, bool fz, bool flag) { 44   if(l == 0) { 45     if(pre % 2 == 0) { 46       if(con % 2 == 0) return 0; 47       if(con % 2 == 1) return 1; 48     } 49     else { 50       if(con % 2 == 0) return 1; 51       if(con % 2 == 1) return 0; 52     } 53   } 54   if(!flag && ~dp[l][pre][con][fz]) return dp[l][pre][con][fz]; 55   LL ret = 0; 56   int pos = flag ? digit[l] : 9; 57   if(fz) { 58     Rep(i, pos+1) { 59       ret += dfs(l-1, i%2, 1, fz&&(i==0), flag&&(i==pos)); 60     } 61   } 62   else if((pre + con) % 2 == 1) { 63     Rep(i, pos+1) { 64       if((i + pre) % 2 == 0) { 65         ret += dfs(l-1, i%2, (con+1)%2, fz&&(i==0), flag&&(i==pos)); 66       } 67       else { 68         ret += dfs(l-1, i%2, 1, fz&&(i==0), flag&&(i==pos)); 69       } 70     } 71   } 72   else { 73     Rep(i, pos+1) { 74       if((i + pre) % 2 == 0) { 75         ret += dfs(l-1, i%2, (con+1)%2, fz&&(i==0), flag&&(i==pos)); 76       } 77     } 78   } 79   if(!flag) dp[l][pre][con][fz] = ret; 80   return ret; 81 } 82  83 LL f(LL x) { 84   int pos = 0; 85   while(x) { 86     digit[++pos] = x % 10; 87     x /= 10; 88   } 89   return dfs(pos, 0, 1, true, true); 90 } 91  92 signed main() { 93   //FRead(); 94   int T, _ = 1; 95   Rint(T); 96   Clr(dp, -1); 97   W(T) { 98     cin >> l >> r; 99     printf("Case #%d: ", _++);100     cout << f(r) - f(l-1) << endl;101   }102   RT 0;103 }