#include<iostream>

 #include<stdio.h>

 #include<algorithm>

 #include<iomanip>

 #include<cmath>

 #include<cstring>

 #include<vector>

 #define ll __int64

 #define pi acos(-1.0)

 #define MAX 50000

 using namespace std;

 int bit[],dp[][][][];

 int dfs(int pos,int num,int mod,int sum,bool f)

 {

     if(pos==-) return mod==sum&&num==;

     if(!f&&dp[pos][mod][num][sum]!=-) return dp[pos][mod][num][sum];

     int ans=;

     int e=f?bit[pos]:;

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

         ans+=dfs(pos-,(*num+i)%mod,mod,sum+i,f&&i==bit[pos]);

     }

     if(!f) dp[pos][mod][num][sum]=ans;

     return ans;

 }

 int cal(int n)

 {

     int m=;

     while(n){

         bit[m++]=n%;

         n/=;

     }

     int ans=;

     for(int i=;i<=*m;i++)

         ans+=dfs(m-,,i,,);

     return ans;

 }

 int main(){

     int t,n,m,ca=;

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

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&m);

         printf("Case %d: %d\n",++ca,cal(m)-cal(n-));

     }

     return ;

 }