3비트 컴퓨터

바이트 왕국의 과학자들이 새로운 종류의 기계, 곧 3비트 컴퓨터(TBC)를 만들기로 했다. 많은 이들은 이 기계가 보통 컴퓨터로는 너무 어려운 문제들까지 풀어 줄 것이라 기대한다. 개발 과정에서 과학자들은 여러 기술적 난관에 부딪혔고, 그중 하나를 해결하도록 돕는 것이 여러분의 임무다.

지금 이들은 메모리 초기화 절차를 다루고 있다. TBC에는 $1, \dots, n$번으로 번호가 매겨진 $n$개의 메모리 비트가 있다. 각 비트는 세 값($a$, $b$, $c$) 중 하나를 갖거나 아직 초기화되지 않은 상태다. TBC는 다음 두 가지 초기화 연산을 제공한다.

• 연속한 두 비트가 모두 초기화되지 않았다면, 그 두 비트에 서로 다른 두 값을 지정할 수 있다.
• 연속한 두 비트 중 하나가 초기화되지 않았고 다른 하나가 값 $x$를 가지고 있다면, 그 두 비트에 서로 다른 두 값을 지정할 수 있으며 두 값 모두 $x$와 달라야 한다 (값 $x$를 갖고 있던 비트도 함께 덮어써진다).

예를 들어 $n = 4$일 때 다음은 올바른 초기화 순서 하나다. 여기서 $u$는 초기화되지 않은 비트를 뜻한다.

$uuuu \rightarrow uuab \rightarrow ucbb \rightarrow babb$

메모리가 최종적으로 가져야 할 값들을 읽어들여, 그러한 초기화가 가능한지 판정하고 답을 출력하는 프로그램을 작성하여라.

입력에는 $1$개 이상 $10$개 이하의 목표 메모리 구성이 주어진다. 첫 줄에는 구성의 개수를 나타내는 정수 하나가 있다. 이어서 각 구성은 두 줄로 주어진다. 첫 줄에는 $i$번째 구성의 메모리 크기를 나타내는 정수 $l_i$ ($1 \le l_i \le 100000$)가 있다. 둘째 줄에는 도달하려는 구성을 나타내는, 문자 $a$, $b$, $c$로 이루어진 길이 $l_i$의 문자열이 있다.

각 구성마다 한 줄씩 출력한다. $i$번째 구성에 대해 초기화가 가능하면 TAK을, 불가능하면 NIE를 출력한다.