#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int digit[];

 ll dp[][];

 ll dfs(int pos,int pre,int doing)

 {

     if(pos==-){

         return pre==;

     }

     if(!doing&&dp[pos][pre]!=-){

         return dp[pos][pre];

     }

     int end=doing?digit[pos]:;

     ll ans=;

     for(int i=;i<=end;i++){

         int npre=(pre+i)%;

         ans+=dfs(pos-,npre,doing&&i==end);

     }

     if(!doing){

         dp[pos][pre]=ans;

     }

     return ans;

 }

 ll Solve(ll n)

 {

     int pos=;

     while(n){

         digit[pos++]=n%;

         n/=;

     }

     return dfs(pos-,,);

 }

 int main()

 {

     ll a,b;

     int t=,_case;

     memset(dp,-,sizeof(dp));

     scanf("%d",&_case);

     while(_case--){

         scanf("%I64d%I64d",&a,&b);

         printf("Case #%d: ",t++);

         if(a==){

             printf("%I64d\n",Solve(b));

         }else

             printf("%I64d\n",Solve(b)-Solve(a-));

     }

     return ;

 }