#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<vector>#include<set>#include<queue>#include<string>#include<algorithm>#define MAXSIZE 70000#define LL long longusing namespace std;const long long INF = 1e18;//给一个B进制的数，一个10进制的数K，B进制数有x位，//对着x位进行全排列的话，有x！种可能，//问这x！的可能中，有多少种可以整除K，各个位置上的数字都不同。LL dp[MAXSIZE][30];int b,k,bit[MAXSIZE],len;char str[MAXSIZE];LL dfs(int pos,int st,int mod){    if(pos < 0)        return mod == 0;    if(dp[st][mod] != -1)        return dp[st][mod];    LL ans = 0;    for(int i=0;i<len;i++)    {        if(st & (1<<i))            continue;        else        {            ans += dfs(pos-1,st|(1<<i),((mod*b)+bit[i])%k);        }    }    dp[st][mod] = ans;    return ans;}LL Solve(){    memset(dp,-1,sizeof(dp));    len = strlen(str);    int pos = 0;    for(int i=0;i<len;i++)    {        if(str[i] >=‘0‘ && str[i] <= ‘9‘)            bit[pos++] = str[i] - ‘0‘;        else            bit[pos++] = str[i] - ‘A‘ + 10;    }    LL ans = dfs(pos-1,0,0);    return ans;}int main(){    int T,cns=1;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&b,&k);        scanf("%s",str);        LL ans = Solve();        printf("Case %d: %lld\n",cns++,ans);    }    return 0;}