#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define FILL(a,b) memset(a,b,sizeof(a))

 typedef long long ll;

 int base,k,len,num[];

 ll dp[<<][];

 char str[];

 ll dfs(int state,int mod)

 {

     if(state==(<<len)-){

         return mod==;

     }

     if(dp[state][mod]!=-)return dp[state][mod];

     ll ans=;

     for(int i=len-;i>=;i--){

         if(!(state&(<<i))){

             ans+=dfs(state|(<<i),(mod*base+num[i])%k);

         }

     }

     return dp[state][mod]=ans;

 }

 int main()

 {

     int _case,t=;

     scanf("%d",&_case);

     while(_case--){

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

         scanf("%s",str);

         len=strlen(str);

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

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

             else num[i]=str[i]-'A'+;

         }

         FILL(dp,-);

         printf("Case %d: %lld\n",t++,dfs(,));

     }

     return ;

 }