피보나치 게임

피보나치 단어 $f_i$를 다음과 같이 정의한다. $f_1 = a$, $f_2 = b$이고, $i \ge 3$일 때 $f_i = f_{i-2} f_{i-1}$이다. 즉 번호가 $i$인 피보나치 단어는 번호가 $i-2$인 단어와 $i-1$인 단어를 순서대로 이어 붙여서 만든다. 예를 들어 $f_3 = ab$, $f_4 = bab$, $f_5 = abbab$이다.

피보나치 게임은 두 사람이 한다. 두 사람은 a와 b로만 이루어진 하나의 단어(이 단어를 판이라고 부른다) 위에서 게임을 한다. 두 사람은 번갈아 가며 수를 두며, 한 번의 수는 판의 오른쪽 끝에서 임의의 피보나치 단어 하나를 지우는 것이다. 더 이상 수를 둘 수 없는 사람이 진다. 주어진 단어에 대해, 먼저 두는 사람이 (두 사람 모두 최선을 다할 때) 항상 이길 수 있는지 판정하라.

테스트 케이스의 개수를 입력받아, 각 테스트 케이스마다 게임을 진행할 단어를 표준 입력에서 읽고, 먼저 두는 사람이 항상 이길 수 있는지 판정하여 그 결과를 표준 출력에 출력하는 프로그램을 작성하라.

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 10$)가 주어진다. 이어지는 $t$개의 줄에 각 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 양의 정수 $n$ ($1 \le n \le 100\,000$)이 주어지고, 공백 한 칸 뒤에 a와 b로 이루어진 길이 $n$의 문자열이 (글자 사이에 공백 없이) 이어진다. 이 문자열이 게임을 진행할 판이다.

$t$개의 줄을 출력한다. 각 줄에는 입력에 주어진 것과 같은 순서로 각 테스트 케이스에 대한 답을 출력한다. 먼저 두는 사람이 항상 이길 수 있으면 TAK을, 그렇지 않으면 NIE를 출력한다.