The Fibonacci Game

Define the Fibonacci words $f_i$ as follows: $f_1 = a$, $f_2 = b$, and for $i \ge 3$, $f_i = f_{i-2} f_{i-1}$. In other words, the Fibonacci word with index $i$ is obtained by concatenating the words with indices $i-2$ and $i-1$, in that order. For example, $f_3 = ab$, $f_4 = bab$, and $f_5 = abbab$.

The Fibonacci game is played by two players on a single word made only of the letters a and b (this word is called the board). The players alternate moves; a single move consists of erasing any one Fibonacci word from the right end of the board. A player who cannot make a move loses. For a given word, determine whether the player who moves first can always win, assuming both players play optimally.

Write a program that reads the number of test cases and, for each one, reads the board on which the game is played from standard input, determines whether the first player can always win, and prints the answer to standard output.

The first line contains one integer $t$ ($1 \le t \le 10$), the number of test cases. Each of the next $t$ lines describes one test case. Each line contains a positive integer $n$ ($1 \le n \le 100\,000$), followed by a single space and then a string of the letters a and b of length $n$ (with no spaces between the letters). This string is the board on which the game is played.

Print $t$ lines. Each line contains the answer for one test case, in the same order as the input. Print TAK if the first player can always win, and NIE otherwise.