#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 long

using namespace std;

const long long INF = 1e18;

//给一个B进制的数，一个10进制的数K，B进制数有x位，

//对着x位进行全排列的话，有x！种可能，

//问这x！的可能中，有多少种可以整除K，各个位置上的数字都不同。

LL dp[MAXSIZE][];

int b,k,bit[MAXSIZE],len;

char str[MAXSIZE];

LL dfs(int pos,int st,int mod)

{

    if(pos < )

        return mod == ;

    if(dp[st][mod] != -)

        return dp[st][mod];

    LL ans = ;

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

    {

        if(st & (<<i))

            continue;

        else

        {

            ans += dfs(pos-,st|(<<i),((mod*b)+bit[i])%k);

        }

    }

    dp[st][mod] = ans;

    return ans;

}

LL Solve()

{

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

    len = strlen(str);

    int pos = ;

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

    {

        if(str[i] >='' && str[i] <= '')

            bit[pos++] = str[i] - '';

        else

            bit[pos++] = str[i] - 'A' + ;

    }

    LL ans = dfs(pos-,,);

    return ans;

}

int main()

{

    int T,cns=;

    scanf("%d",&T);

    while(T--)

    {

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

        scanf("%s",str);

        LL ans = Solve();

        printf("Case %d: %lld\n",cns++,ans);

    }

    return ;

}