#include <stdio.h>

#include <vector>

#include <string.h>

using namespace std;

vector <int> num;

int dp[][];

//dp状态设计成dp[pos][remain]，remain表示还剩多少fA可以分配

int dfs(int pos, int remain, bool limit) //limit表示后面的数是否能乱填

{

    if (pos == -) return remain >= ;

    if (!limit && ~dp[pos][remain]) return dp[pos][remain];

    int end = limit?num[pos]:;

    int res = ;

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

    {

        res += dfs(pos-, remain-(<<pos)*i, limit && (i == end));

    }

    if (!limit) dp[pos][remain] = res;

    return res;

}

int main()

{

    int t;

    scanf("%d", &t);

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

    for (int ca = ; ca <= t; ca ++)

    {

        int A, B;

        scanf("%d %d", &A, &B);

        num.clear();

        while(B)

        {

            num.push_back(B % );

            B /= ;

        }

        int fa = ;

        for (int i = ; A; A /= , ++ i) fa += ( << i) * (A % );

        printf("Case #%d: %d\n", ca, dfs(num.size()-, +fa, ));

    }

    return ;

}