#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#define REP(I,A,B) for(register int I=A,_END_=B;I<=_END_;I++)
#define REPD(I,A,B) for(register int I=A,_END_=B;I>=_END_;I--)
#define RI(X) X=Readint()
#define RII(X,Y) RI(X),RI(Y)
#define RIII(X,Y,Z) RI(X),RI(Y),RI(Z)
#define RS(X) scanf("%s",X)
#define RD(X) scanf("%lf",&X)
#define GCH getchar()
#define PCH(X) putchar(X)
#define MS(X,Y) memset(X,Y,sizeof(X))
#define MC(X,Y,var,len) memcpy(X,Y,sizeof(var)*(len))
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define pb(X) push_back(X)
#define mp(A,B) make_pair(A,B)
#define ts first
#define sc second
#define lch(p) (p+p)
#define rch(p) (p+p+1)
#define lowbit(X) ((X)&(-(X)))
using namespace std;
typedef pair<int,int> poi;
inline int Readint()
{
int ret=0;
int f=1;
char ch;
do
{
ch=GCH;
if (ch=='-') f*=-1;
}while(ch>=0 && (ch<'0' || ch>'9'));
while ('0'<=ch && ch<='9')
{
ret=ret*10+ch-'0';
ch=GCH;
}
return ret*f;
}
void open()
{
freopen("gen.in","r",stdin);
freopen("gen.out","w",stdout);
}
void close()
{
fclose(stdin);
fclose(stdout);
}
const int MAXN = 105;
const int inf = 1000;
int pw[30]={1};
int f[27][27]={0};
int g[MAXN][MAXN]={0};
int ans[MAXN]={0};
char str[MAXN]={0};
int n;
int len;
void prepare()
{
RI(n);
char change[10];
pw[0]=1;
REP(i,1,25) pw[i]=pw[i-1]<<1;
REP(i,1,n)
{
RS(change);
change[0]-='A';
change[1]-='A';
change[2]-='A';
f[change[1]][change[2]]|=pw[change[0]];
}
}
void init()
{
RS(str+1);
MS(g,0);
len=strlen(str+1);
ans[0]=0;
REP(i,1,len) ans[i]=inf,str[i]-='A';
}
inline int log2(const int &k)
{
if (k==1) return 0;
if (k==2) return 1;
if (k==4) return 2;
if (k==8) return 3;
if (k==16) return 4;
if (k==32) return 5;
if (k==64) return 6;
if (k==128) return 7;
if (k==256) return 8;
if (k==512) return 9;
if (k==1024) return 10;
if (k==2048) return 11;
if (k==4096) return 12;
if (k==8192) return 13;
if (k==16384) return 14;
if (k==32768) return 15;
if (k==65536) return 16;
if (k==131072) return 17;
if (k==262144) return 18;
if (k==524288) return 19;
if (k==1048576) return 20;
if (k==2097152) return 21;
if (k==4194304) return 22;
if (k==8388608) return 23;
if (k==16777216) return 24;
if (k==33554432) return 25;
}
inline int merge(int u,int v)
{
register int ch1,ch2,t;
register int ret=0;
for (;u;u&=u-1)
{
ch1=(int)log2(lowbit(u));
for (t=v;t;t&=t-1)
{
ch2=(int)log2(lowbit(v));
ret|=f[ch1][ch2];
}
}
return ret;
}
inline void init_dynamic()
{
REP(i,1,len)
g[i][i]=pw[str[i]];
register int j;
REP(l,2,len)
REP(i,1,len-l+1)
{
j=i+l-1;
REP(k,i,j-1)
g[i][j]|=merge(g[i][k],g[k+1][j]);
}
}
const int S=262144;
inline void dynamic()
{
REP(i,0,len-1)
if (ans[i]!=inf)
REP(j,i+1,len)
if (g[i+1][j]&S)
ans[j]=min(ans[j],ans[i]+1);
if (ans[len]==inf)
printf("NIE\n");
else
printf("%d\n",ans[len]);
}
int main()
{
// open();
int _=0;
prepare();
RI(_);
REP(__,1,_)
{
init();
init_dynamic();
dynamic();
}
close();
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx2ZWN0b3I+CgojZGVmaW5lIFJFUChJLEEsQikgZm9yKHJlZ2lzdGVyIGludCBJPUEsX0VORF89QjtJPD1fRU5EXztJKyspCiNkZWZpbmUgUkVQRChJLEEsQikgZm9yKHJlZ2lzdGVyIGludCBJPUEsX0VORF89QjtJPj1fRU5EXztJLS0pCiNkZWZpbmUgUkkoWCkgWD1SZWFkaW50KCkKI2RlZmluZSBSSUkoWCxZKSBSSShYKSxSSShZKQojZGVmaW5lIFJJSUkoWCxZLFopIFJJKFgpLFJJKFkpLFJJKFopCiNkZWZpbmUgUlMoWCkgc2NhbmYoIiVzIixYKQojZGVmaW5lIFJEKFgpIHNjYW5mKCIlbGYiLCZYKQojZGVmaW5lIEdDSCBnZXRjaGFyKCkKI2RlZmluZSBQQ0goWCkgcHV0Y2hhcihYKQojZGVmaW5lIE1TKFgsWSkgbWVtc2V0KFgsWSxzaXplb2YoWCkpCiNkZWZpbmUgTUMoWCxZLHZhcixsZW4pIG1lbWNweShYLFksc2l6ZW9mKHZhcikqKGxlbikpCiNkZWZpbmUgZGVidWcoLi4uKSBmcHJpbnRmKHN0ZGVycixfX1ZBX0FSR1NfXykKI2RlZmluZSBwYihYKSBwdXNoX2JhY2soWCkKI2RlZmluZSBtcChBLEIpIG1ha2VfcGFpcihBLEIpCiNkZWZpbmUgdHMgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKI2RlZmluZSBsY2gocCkgKHArcCkKI2RlZmluZSByY2gocCkgKHArcCsxKQojZGVmaW5lIGxvd2JpdChYKSAoKFgpJigtKFgpKSkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8aW50LGludD4gcG9pOwoKaW5saW5lIGludCBSZWFkaW50KCkKewoJaW50IHJldD0wOwoJaW50IGY9MTsKCWNoYXIgY2g7CglkbwoJewoJCWNoPUdDSDsKCQlpZiAoY2g9PSctJykgZio9LTE7Cgl9d2hpbGUoY2g+PTAgJiYgKGNoPCcwJyB8fCBjaD4nOScpKTsKCQoJd2hpbGUgKCcwJzw9Y2ggJiYgY2g8PSc5JykKCXsKCQlyZXQ9cmV0KjEwK2NoLScwJzsKCQljaD1HQ0g7Cgl9CglyZXR1cm4gcmV0KmY7Cn0KCnZvaWQgb3BlbigpCnsKCWZyZW9wZW4oImdlbi5pbiIsInIiLHN0ZGluKTsKCWZyZW9wZW4oImdlbi5vdXQiLCJ3IixzdGRvdXQpOwp9CnZvaWQgY2xvc2UoKQp7CglmY2xvc2Uoc3RkaW4pOwoJZmNsb3NlKHN0ZG91dCk7Cn0KCmNvbnN0IGludCBNQVhOID0gMTA1Owpjb25zdCBpbnQgaW5mID0gMTAwMDsKCmludCBwd1szMF09ezF9OwoKaW50IGZbMjddWzI3XT17MH07CmludCBnW01BWE5dW01BWE5dPXswfTsKCmludCBhbnNbTUFYTl09ezB9OwoKY2hhciBzdHJbTUFYTl09ezB9OwoKaW50IG47CmludCBsZW47Cgp2b2lkIHByZXBhcmUoKQp7CglSSShuKTsKCWNoYXIgY2hhbmdlWzEwXTsKCXB3WzBdPTE7CglSRVAoaSwxLDI1KSBwd1tpXT1wd1tpLTFdPDwxOwoJCglSRVAoaSwxLG4pCgl7CgkJUlMoY2hhbmdlKTsKCQljaGFuZ2VbMF0tPSdBJzsKCQljaGFuZ2VbMV0tPSdBJzsKCQljaGFuZ2VbMl0tPSdBJzsKCQlmW2NoYW5nZVsxXV1bY2hhbmdlWzJdXXw9cHdbY2hhbmdlWzBdXTsKCX0KfQoKdm9pZCBpbml0KCkKewoJUlMoc3RyKzEpOwoJTVMoZywwKTsKCWxlbj1zdHJsZW4oc3RyKzEpOwoJYW5zWzBdPTA7CglSRVAoaSwxLGxlbikgYW5zW2ldPWluZixzdHJbaV0tPSdBJzsKfQoKaW5saW5lIGludCBsb2cyKGNvbnN0IGludCAmaykKewoJaWYgKGs9PTEpIHJldHVybiAwOwoJaWYgKGs9PTIpIHJldHVybiAxOwoJaWYgKGs9PTQpIHJldHVybiAyOwoJaWYgKGs9PTgpIHJldHVybiAzOwoJaWYgKGs9PTE2KSByZXR1cm4gNDsKCWlmIChrPT0zMikgcmV0dXJuIDU7CglpZiAoaz09NjQpIHJldHVybiA2OwoJaWYgKGs9PTEyOCkgcmV0dXJuIDc7CglpZiAoaz09MjU2KSByZXR1cm4gODsKCWlmIChrPT01MTIpIHJldHVybiA5OwoJaWYgKGs9PTEwMjQpIHJldHVybiAxMDsKCWlmIChrPT0yMDQ4KSByZXR1cm4gMTE7CglpZiAoaz09NDA5NikgcmV0dXJuIDEyOwoJaWYgKGs9PTgxOTIpIHJldHVybiAxMzsKCWlmIChrPT0xNjM4NCkgcmV0dXJuIDE0OwoJaWYgKGs9PTMyNzY4KSByZXR1cm4gMTU7CglpZiAoaz09NjU1MzYpIHJldHVybiAxNjsKCWlmIChrPT0xMzEwNzIpIHJldHVybiAxNzsKCWlmIChrPT0yNjIxNDQpIHJldHVybiAxODsKCWlmIChrPT01MjQyODgpIHJldHVybiAxOTsKCWlmIChrPT0xMDQ4NTc2KSByZXR1cm4gMjA7CglpZiAoaz09MjA5NzE1MikgcmV0dXJuIDIxOwoJaWYgKGs9PTQxOTQzMDQpIHJldHVybiAyMjsKCWlmIChrPT04Mzg4NjA4KSByZXR1cm4gMjM7CglpZiAoaz09MTY3NzcyMTYpIHJldHVybiAyNDsKCWlmIChrPT0zMzU1NDQzMikgcmV0dXJuIDI1Owp9CgoKaW5saW5lIGludCBtZXJnZShpbnQgdSxpbnQgdikKewoJcmVnaXN0ZXIgaW50IGNoMSxjaDIsdDsKCXJlZ2lzdGVyIGludCByZXQ9MDsKCWZvciAoO3U7dSY9dS0xKQoJewoJCWNoMT0oaW50KWxvZzIobG93Yml0KHUpKTsKCQlmb3IgKHQ9djt0O3QmPXQtMSkKCQl7CgkJCWNoMj0oaW50KWxvZzIobG93Yml0KHYpKTsKCQkJcmV0fD1mW2NoMV1bY2gyXTsKCQl9Cgl9CglyZXR1cm4gcmV0Owp9CgppbmxpbmUgdm9pZCBpbml0X2R5bmFtaWMoKQp7CglSRVAoaSwxLGxlbikKCQlnW2ldW2ldPXB3W3N0cltpXV07CglyZWdpc3RlciBpbnQgajsKCVJFUChsLDIsbGVuKQoJCVJFUChpLDEsbGVuLWwrMSkKCQl7CgkJCWo9aStsLTE7CgkJCVJFUChrLGksai0xKQoJCQkJZ1tpXVtqXXw9bWVyZ2UoZ1tpXVtrXSxnW2srMV1bal0pOwoJCX0KfQpjb25zdCBpbnQgIFM9MjYyMTQ0OyAKaW5saW5lIHZvaWQgZHluYW1pYygpCnsKCVJFUChpLDAsbGVuLTEpCgkJaWYgKGFuc1tpXSE9aW5mKQoJCQlSRVAoaixpKzEsbGVuKQoJCQkJaWYgKGdbaSsxXVtqXSZTKQoJCQkJCWFuc1tqXT1taW4oYW5zW2pdLGFuc1tpXSsxKTsKCWlmIChhbnNbbGVuXT09aW5mKQoJCXByaW50ZigiTklFXG4iKTsKCWVsc2UKCQlwcmludGYoIiVkXG4iLGFuc1tsZW5dKTsKfQoKaW50IG1haW4oKQp7Ci8vCW9wZW4oKTsKCWludCBfPTA7CglwcmVwYXJlKCk7CglSSShfKTsKCVJFUChfXywxLF8pCgl7CgkJaW5pdCgpOwoJCWluaXRfZHluYW1pYygpOwoJCWR5bmFtaWMoKTsKCX0KCWNsb3NlKCk7CglyZXR1cm4gMDsKfQ==