#include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <string>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e4+;

 int dp[][maxn];    //pos sum

 int Max;

 int aa[];

 int f(int x){

     int ans = ;

     int cnt = ;

     while(x){

         ans = ans + x%*cnt;

         x /= ;

         cnt *= ;

     }

     return ans;

 }

 int dfs(int pos, int sum, bool limit){

     if(pos == -) return sum <= Max;    //是否满足条件

     if(sum > Max) return ;

     if(!limit && dp[pos][Max - sum] != -)

         return dp[pos][Max - sum];

     int up = limit?aa[pos]:;

     int ans = ;

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

         ans += dfs(pos-, sum+ i*(<<pos), limit&&i == aa[pos]);

     }

     if(!limit) dp[pos][Max - sum] = ans;

     return ans;

 }

 int solve(int x){

     int pos = ;

     while(x){

         aa[pos++] = x%;

         x /= ;

     }

     return dfs(pos-, , true);    //最高位是有限制的

 }    

 int main(){

     memset(dp, -, sizeof dp);

     int t;

     scanf("%d", &t);

     int Case = ;

     while(t--){

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

         Case++;

         int a, b;

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

         Max = f(a);

         int ans = solve(b);

         printf("Case #%d: %d\n", Case, ans);

     }

     return ;

 }