#include <iostream>

#define ll long long
#define db(x) cout << "> " << #x << " : " << x << endl;

const int B = 16;
const int K = 20;
using namespace std;

ll dp[(1 << B) +10][K +2];

int get_digit(char c)
{
	if('0' <= c && c <= '9')
		return (c -'0');
	
	return int(c -'A') +10;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int tests;
	cin >> tests;
	
	for(int tt = 1; tt <= tests; tt++)
	{
		int base, k;
		cin >> base >> k;
		
		string s;
		cin >> s;
		
		int n = s.size();
		
		dp[0][0] = 1;
	
		for(int mask = 0; mask < (1 << n); mask++)
		{
			for(int rem = 0; rem < k; rem++)
			{
				for(int idx = 0; idx < n; idx++)
				{
					if(mask & (1 << idx))
						continue;
					
					int dig = get_digit(s[idx]);
					dp[mask | (1 << idx)][(rem *base +dig) % k] += dp[mask][rem];
				}
			}
		}
		
		cout << "Case " << tt << ": " << dp[(1 << n) -1][0] << '\n';

		for(int mask = 0; mask < (1 << n); mask++)
			for(int rem = 0; rem < k; rem++)
				dp[mask][rem] = 0;
	}
	
	return 0;
}