#include <cstdio>#include <cstdlib>#include <climits>#include <cstring>#include <cmath>#include <algorithm>#include<iostream>#include<queue>#include <map>using namespace std;typedef long long ll;#define INF (INT_MAX/10)#define SQR(x) ((x)*(x))#define rep(i, n) for (int i=0; i<(n); ++i)#define repf(i, a, b) for (int i=(a); i<=(b); ++i)#define repd(i, a, b) for (int i=(a); i>=(b); --i)#define clr(ar,val) memset(ar, val, sizeof(ar))#define pb(i) push_back(i)#define N 15int n,m;char s[N];ll a[N][N];int next[N];bool vis[30];void kmp(){memset(next,-1,sizeof(next));int j=-1;int len=strlen(s);rep(i,len){while(j!=-1 && s[i]!=s[j] ) j=next[j];next[i+1]=++j;}next[0]=0;}void solve(){ kmp();memset(a,0,sizeof(a));memset(vis,false,sizeof(vis));vector<int>vec;int len=strlen(s);rep(i,len)if(vis[s[i]-'A']==false) vec.pb(s[i]),vis[s[i]-'A']=true;int mm=vec.size();rep(i,len){a[i][i]-=n;a[i][len+1]=n;a[i][0]+=n-mm;rep(j,mm){int x=vec[j]; if(x==s[i]) a[i][i+1]++;else{ int k=next[i]; while(k!=0 && s[k]!=x) k=next[k]; if(s[k]==x) a[i][k+1]++; else a[i][0]++;}}}}void guess(){ rep(i,n){int k=-1;repf(j,i,n-1) if(a[j][i]!=0){k=j;break;}if(k==-1) continue;if(k!=i) rep(j,m) swap(a[i][j],a[k][j]);rep(j,n){if(j!=i){int x=a[i][i],y=a[j][i];rep(k,m)a[j][k]=a[j][k]*x-a[i][k]*y;}}}if(a[0][0]==0) cout<<0<<endl;cout<<-a[0][m-1]/a[0][0]<<endl;}int main(){int test;scanf("%d",&test);repf(i,1,test){if(i!=1) printf("n");printf("Case %d:n",i);scanf("%d",&n);scanf("%s",s);m=strlen(s)+2;solve();n=strlen(s); guess();}return 0;}
