#include<bits/stdc++.h>

using namespace std;

int f2[];

int b[];

int dp[][];

int A;

int F(int x)

{

    int a[];

    int cnt=;

    int ret=;

    do{

        a[cnt]=x%;

        x/=;

        cnt++;

    }while (x);

    for (int i=cnt-;i>=;i--)

    {

        ret=ret*+a[i];

    }

    return ret;

}

int dfs(int pos,int preok,int limit)

{

    if (pos==-) return ;

    if (preok && dp[pos][limit]!=-) return dp[pos][limit];

    int up=preok?:b[pos];

    int ans=;

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

    {

        if (limit-f2[pos]*i<) continue;

        if (i<b[pos]||preok) ans+=dfs(pos-,,limit-f2[pos]*i);

        else ans+=dfs(pos-,,limit-f2[pos]*i);

    }

    if (preok) dp[pos][limit]=ans;

    return ans;

}

int solve(int n)

{

    if (n<) return ;

    int cnt=;

    int now=n;

    do{

        b[cnt]=now%;

        now/=;

        cnt++;

    }while (now);

    return dfs(cnt-,,F(A));

}

int main()

{

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

    f2[]=;

    for (int i=;i<=;i++) f2[i]=f2[i-]*;

    int t;

    scanf("%d",&t);

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

    {

        int n;

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

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

    }

    return ;

}