import collections
import sys

INFINITY= 2000000000
NIL = 0

class BipartiteGraph:
    U,V =0,0
    Adj = [[]]
    Dist,PairU,PairV = [],[],[]
    Q = collections.deque([])

    def __init__(self,u,v):
        self.U=u+1
        self.V=v+1
        self.Adj = [[] for x in range(self.U)]
        self.Dist = [0 for i in range(self.U)]
        self.PairU,self.PairV = [NIL for i in range(self.U)], [NIL for i in range(self.V)]

    def bfs(self):
        for u in range(1,self.U):
            if self.PairU[u] == NIL:
                self.Dist[u] = 0
                self.Q.append(u)
            else:
                self.Dist[u] = INFINITY
        self.Dist[NIL] = INFINITY

        while self.Q:
            u = self.Q.popleft()
            if u > NIL:
                for v in self.Adj[u]:
                    if self.Dist[self.PairV[v]] == INFINITY:
                        self.Dist[self.PairV[v]] = self.Dist[u] + 1
                        self.Q.append(self.PairV[v])
        return self.Dist[NIL] < INFINITY

    def dfs(self,u):
        if u!=NIL:
            for v in self.Adj[u]:
                if self.Dist[self.PairV[v]] == self.Dist[u] + 1:
                    if self.dfs(self.PairV[v]):
                        self.PairV[v] = u
                        self.PairU[u] = v
                        return True
            self.Dist[u] = INFINITY
            return False
        else:
            return True

    def addEdge(self,u,v):
        self.Adj[u].append(v)

    def HopcroftKarp(self):
        matchingSize = 0
        while self.bfs():
            for u in range(1,self.U):
                if self.PairU[u]==NIL:
                    if self.dfs(u):
                        matchingSize+=1
        return matchingSize

def getDice():
    return set(input().split(' '))

def test():
    u = int(input())
    s = input()
    LetterEdges = [[] for x in range(26)]
    BG = BipartiteGraph(len(s),u)
    for i in range(u):
        A = getDice()
        for a in A:
            LetterEdges[ord(a) - ord('A')].append(i+1)
    for i in range(len(s)):
        chara = int(ord(s[i]) - ord('A'))
        for dicenumber in LetterEdges[chara]:
            BG.addEdge(i+1,dicenumber)
    result = len(s)-BG.HopcroftKarp()
    if result>0:
        print(result)
    else:
        print("TAK")


Tau = int(input())
for testnumber in range(Tau):
    test()