/*In the name of Almighty Allah*/
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define Fill(a,b) memset (a, b, sizeof a)
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define mod 1000000007
#define For(i,a,b) for(int i=a;i<b;i++)
#define rof(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
void dbga ( int a[], int s )
{
For ( i, 0, s ) cout << a[i] << " ";
cout << endl;
}
void dbgv ( vector < int > v )
{
For ( i, 0, sz(v) ) cout << v[i] << " ";
cout << endl;
}
void rev ( int a[], int s )
{
for ( int i = 0,j = s-1; i < s/2; i++, j-- ) {
swap ( a[i], a[j] );
}
}
string to_s(int t)
{
stringstream ss;
ss << t;
return ss.str();
}
unsigned long long mypow ( int a, int b )
{
unsigned long long ret = 1;
For ( i, 1, b+1 ) {
ret *= a;
}
return ret;
}
struct edge {
int w,s;
};
bool cmp ( const edge &a, const edge &b )
{
return a.w < b.w;
}
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int tx[] = { 1, -1, 0, 0 };
int ty[] = { 0, 0, 1, -1 };
/*
bool isprime[100123];
vector < int > prime;
void seive ()
{
int num = 100000, sqr = 340;
for ( int i = 3; i <= num; i+=2 ) isprime[i] = 1;
for ( int i = 3; i <= sqr; i+=2 ) {
if ( isprime[i] ) {
for ( int j = i * i; j <=num; j+=(i*2) ) {
isprime[j] = 0;
}
}
}
prime.pb ( 2 );
isprime[2] = 1;
for ( int i = 3; i <=num; i+=2 ) {
if ( isprime[i] ) prime.pb ( i );
}
}
*/
unsigned long long dp[1<<16][22];
int n, base, k, a[20], p;
char s[17];
unsigned long long call ( int mask, int md )
{
if ( mask == (1<<n)-1 ) {
return ( md == 0 );
}
if ( dp[mask][md] != -1 ) return dp[mask][md];
int num = md, pos = 0;
unsigned long long ret = 0;
For ( i, 1, n ) if ( check ( mask, i ) ) pos++;
rof ( i, n-1, 0 ) {
if ( check ( mask, i ) == 0 ) {
if ( base != 10 ) {
num += ( a[i] ) * mypow ( base, pos );
}
else {
num *= 10;
num += a[i];
}
ret += call ( Set ( mask, i ), num % k );
}
}
return dp[mask][md] = ret;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
scanf ( "%d", &t );
For ( i, 1, t+1 ) {
Fill ( dp, -1 );
scanf ( "%d%d", &base, &k );
scanf ( "%s", &s );
n = strlen ( s );
For ( j, 0, n ) {
a[j] = s[j] - '0';
if ( a[j] > 9 ) a[j] -= 7;
}
printf ( "Case %d: %llu\n", i, call ( 0, 0 ) );
}
return 0;
}
LypJbiB0aGUgbmFtZSBvZiBBbG1pZ2h0eSBBbGxhaCovCgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgoKI2RlZmluZSBwYiAgICAgICAgICBwdXNoX2JhY2sKI2RlZmluZSBtcCAgICAgICAgICBtYWtlX3BhaXIKI2RlZmluZSBGaWxsKGEsYikgbWVtc2V0IChhLCBiLCBzaXplb2YgYSkKI2RlZmluZSBhbGwoYSkgICAgICAoYSkuYmVnaW4oKSwoYSkuZW5kKCkKI2RlZmluZSBGICAgICAgICAgICBmaXJzdAojZGVmaW5lIFMgICAgICAgICAgIHNlY29uZAojZGVmaW5lIHN6KHgpICAgICAgIChpbnQpeC5zaXplKCkKI2RlZmluZSBtb2QgICAgICAgICAxMDAwMDAwMDA3CiNkZWZpbmUgRm9yKGksYSxiKSAgZm9yKGludCBpPWE7aTxiO2krKykKI2RlZmluZSByb2YoaSxhLGIpICBmb3IgKGludCBpPWE7aT49YjtpLS0pCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgICAgICAgbGw7CnR5cGVkZWYgZG91YmxlICAgICAgICAgIGRsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+ICAgICB2aTsKCmludCBTZXQoaW50IE4saW50IHBvcyl7cmV0dXJuIE49TiB8ICgxPDxwb3MpO30KaW50IHJlc2V0KGludCBOLGludCBwb3Mpe3JldHVybiBOPSBOICYgfigxPDxwb3MpO30KYm9vbCBjaGVjayhpbnQgTixpbnQgcG9zKXtyZXR1cm4gKGJvb2wpKE4gJiAoMTw8cG9zKSk7fQoKdm9pZCBkYmdhICggaW50IGFbXSwgaW50IHMgKQp7CiAgICBGb3IgKCBpLCAwLCBzICkgY291dCA8PCBhW2ldIDw8ICIgIjsKICAgIGNvdXQgPDwgZW5kbDsKfQoKdm9pZCBkYmd2ICggdmVjdG9yIDwgaW50ID4gdiApCnsKICAgIEZvciAoIGksIDAsIHN6KHYpICkgY291dCA8PCB2W2ldIDw8ICIgIjsKICAgIGNvdXQgPDwgZW5kbDsKfQoKdm9pZCByZXYgKCBpbnQgYVtdLCBpbnQgcyApCnsKICAgIGZvciAoIGludCBpID0gMCxqID0gcy0xOyBpIDwgcy8yOyBpKyssIGotLSApIHsKICAgICAgICBzd2FwICggYVtpXSwgYVtqXSApOwogICAgfQp9CgoKc3RyaW5nIHRvX3MoaW50IHQpCnsKICBzdHJpbmdzdHJlYW0gc3M7CiAgc3MgPDwgdDsKICByZXR1cm4gc3Muc3RyKCk7Cn0KCnVuc2lnbmVkIGxvbmcgbG9uZyBteXBvdyAoIGludCBhLCBpbnQgYiApCnsKICAgIHVuc2lnbmVkIGxvbmcgbG9uZyAgcmV0ID0gMTsKICAgIEZvciAoIGksIDEsIGIrMSApIHsKICAgICAgICByZXQgKj0gYTsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0KCgpzdHJ1Y3QgZWRnZSB7CiAgICBpbnQgdyxzOwp9OwoKYm9vbCBjbXAgKCBjb25zdCBlZGdlICZhLCBjb25zdCBlZGdlICZiICkKewogICAgcmV0dXJuIGEudyA8IGIudzsKfQoKbGwgZ2NkKGxsIGEsIGxsIGIpIHsgcmV0dXJuICFhID8gYiA6IGdjZChiICUgYSwgYSk7IH0KbGwgbGNtKGxsIGEsIGxsIGIpIHsgcmV0dXJuIGEgLyBnY2QoYSwgYikgKiBiOyB9CgppbnQgdHhbXSA9IHsgMSwgLTEsIDAsIDAgfTsKaW50IHR5W10gPSB7IDAsIDAsIDEsIC0xIH07CgoKLyoKYm9vbCBpc3ByaW1lWzEwMDEyM107CnZlY3RvciA8IGludCA+IHByaW1lOwoKdm9pZCBzZWl2ZSAoKQp7CiAgICBpbnQgbnVtID0gMTAwMDAwLCBzcXIgPSAzNDA7CiAgICBmb3IgKCBpbnQgaSA9IDM7IGkgPD0gbnVtOyBpKz0yICkgaXNwcmltZVtpXSA9IDE7CgogICAgZm9yICggaW50IGkgPSAzOyBpIDw9IHNxcjsgaSs9MiApIHsKICAgICAgICBpZiAoIGlzcHJpbWVbaV0gKSB7CiAgICAgICAgICAgIGZvciAoIGludCBqID0gaSAqIGk7IGogPD1udW07IGorPShpKjIpICkgewogICAgICAgICAgICAgICAgaXNwcmltZVtqXSA9IDA7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgcHJpbWUucGIgKCAyICk7CiAgICBpc3ByaW1lWzJdID0gMTsKCiAgICBmb3IgKCBpbnQgaSA9IDM7IGkgPD1udW07IGkrPTIgKSB7CiAgICAgICAgaWYgKCBpc3ByaW1lW2ldICkgcHJpbWUucGIgKCBpICk7CiAgICB9Cn0KKi8KCnVuc2lnbmVkIGxvbmcgbG9uZyAgZHBbMTw8MTZdWzIyXTsKaW50IG4sIGJhc2UsIGssIGFbMjBdLCBwOwpjaGFyIHNbMTddOwoKdW5zaWduZWQgbG9uZyBsb25nIGNhbGwgKCBpbnQgbWFzaywgaW50IG1kICkKewoKICAgIGlmICggbWFzayA9PSAoMTw8biktMSApIHsKCiAgICAgICAgcmV0dXJuICggbWQgPT0gMCApOwogICAgfQoKICAgIGlmICggZHBbbWFza11bbWRdICE9IC0xICkgcmV0dXJuIGRwW21hc2tdW21kXTsKICAgIGludCAgbnVtID0gbWQsIHBvcyA9IDA7CgogICAgdW5zaWduZWQgbG9uZyBsb25nIHJldCA9IDA7CgogICAgRm9yICggaSwgMSwgbiApIGlmICggY2hlY2sgKCBtYXNrLCBpICkgKSBwb3MrKzsKCgoKICAgIHJvZiAoIGksIG4tMSwgMCApIHsKICAgICAgICBpZiAoIGNoZWNrICggbWFzaywgaSApID09IDAgKSB7CiAgICAgICAgICAgIGlmICggYmFzZSAhPSAxMCApIHsKICAgICAgICAgICAgICAgIG51bSArPSAoIGFbaV0gKSAqIG15cG93ICggYmFzZSwgcG9zICk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBudW0gKj0gMTA7CiAgICAgICAgICAgICAgICBudW0gKz0gYVtpXTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0ICs9IGNhbGwgKCBTZXQgKCBtYXNrLCBpICksIG51bSAlIGsgKTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIGRwW21hc2tdW21kXSA9IHJldDsKfQoKaW50IG1haW4oKQp7CiAgICAvL2ZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKTsKICAgIC8vZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKCiAgICBpbnQgdDsKICAgIHNjYW5mICggIiVkIiwgJnQgKTsKICAgIEZvciAoIGksIDEsIHQrMSApIHsKCiAgICAgICAgRmlsbCAoIGRwLCAtMSApOwoKICAgICAgICBzY2FuZiAoICIlZCVkIiwgJmJhc2UsICZrICk7CiAgICAgICAgc2NhbmYgKCAiJXMiLCAmcyApOwogICAgICAgIG4gPSBzdHJsZW4gKCBzICk7CiAgICAgICAgRm9yICggaiwgMCwgbiApIHsKICAgICAgICAgICAgYVtqXSA9IHNbal0gLSAnMCc7CiAgICAgICAgICAgIGlmICggYVtqXSA+IDkgKSBhW2pdIC09IDc7CgogICAgICAgIH0KCiAgICAgICAgcHJpbnRmICggIkNhc2UgJWQ6ICVsbHVcbiIsIGksIGNhbGwgKCAwLCAwICkgKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=