#include<iostream>
#include<vector> 
#include<queue>
#include<set>
#include<climits>

#define INF INT_MAX
//null vertex
#define NIL 0

using namespace std;

class BipartiteGraph {
public:
	int U, V; //number of points in each part of the graph
	vector<vector<int> > Adj; //adjacency list
	vector<int> Pair_U;
	vector<int> Pair_V;
	vector<int> Dist;
	queue<int> Q;

public:
	BipartiteGraph(int u, int v) {
		U = u + 1;
		V = v + 1;
		Adj = vector<vector <int> >(U, vector<int>(0));
		Pair_U = vector<int>(U, NIL);
		Pair_V = vector<int>(V, NIL);
		Dist = vector<int>(U);
		Q = queue<int>();
	}
	
	bool bfs() {
		for (int u = 1; u < U; u++) {
			if (Pair_U[u] == NIL) {
				Dist[u] = 0;
				Q.push(u);
			}
			else {
				Dist[u] = INF;
			}
		}
		Dist[NIL] = INF;
		while (not Q.empty()) {
			int u = Q.front();
			Q.pop();
			if (u!=NIL) {
				for (int i = 0; i < Adj[u].size(); i++) {
					int v = Adj[u][i];
					if (Dist[Pair_V[v]] == INF) {
						Dist[Pair_V[v]] = Dist[u] + 1;
						Q.push(Pair_V[v]);
					}
				}
			}
		}
		return (Dist[NIL] < INF);
	}

	bool dfs(int u) {
		if (u != NIL) {
			for (int i = 0; i < Adj[u].size(); i++) {
				int v = Adj[u][i];
				if (Dist[Pair_V[v]] == Dist[u] + 1) {
					if (dfs(Pair_V[v])) {
						Pair_V[v] = u;
						Pair_U[u] = v;
						return true;
					}
				}
			}
			Dist[u] = INF;
			return false;
		}
		return true;
	}


	int HopcroftuKarpu() {
		int matchingu = 0;
		while (bfs()) {
			for (int u = 1; u < U; u++) {
				if (Pair_U[u]==NIL && dfs(u)) {
					matchingu = matchingu + 1;
				}
			}
		}
		return matchingu;
	}

	void AddEdge(int u, int v) {
		Adj[u].push_back(v);
	}
};


void test(){
	int u;
	string s;
	cin>>u>>s;
	vector<vector<int> > LetterEdges = vector<vector<int> >(26,vector<int>());
	BipartiteGraph BG = BipartiteGraph(s.size(),u);
	
	set<int> dice = set<int>();
	char side;
	for(int i =1; i<=u; i++){
		for(int sideno=0; sideno<6; sideno++){
			cin>>side;
			dice.insert(side-'A');
		}
		for(set<int>::iterator it = dice.begin(); it!=dice.end(); it++){
			LetterEdges[*it].push_back(i);
		}
		dice.clear();
	}
	int chara;
	for(int i = 0; i <s.size(); i++){
		chara = s[i] - 'A';
		for(int j =0; j<LetterEdges[chara].size(); j++){
			BG.AddEdge(i+1,LetterEdges[chara][j]);
		}
	}
	int A = BG.HopcroftuKarpu();
	if(A==s.size()){
		cout<<"TAK\n";
	}
	else{
		cout<<s.size()-A<<'\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin>>T;
	while(T-->0){
		test();
	}
	return 0;
}
