Three-Bit Computers

Scientists in the Kingdom of Byteland set out to build a new kind of machine, the three-bit computer (TBC). Many expect that it will crack problems far too hard for ordinary computers. Along the way the team hit a number of engineering snags, and your job is to help them clear one of them.

Right now they are working on the memory initialization routine. A TBC has $n$ memory bits numbered $1, \dots, n$. Each bit either holds one of three values ($a$, $b$, or $c$) or is still uninitialized. The machine offers exactly two initialization operations:

• Two consecutive uninitialized bits can be set to two different values.
• Two consecutive bits, one uninitialized and the other holding a value $x$, can be set to two different values, both of which must differ from $x$ (so the bit that held $x$ is overwritten as well).

For example, one valid initialization sequence for $n = 4$ looks like this, where $u$ marks an uninitialized bit:

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

Write a program that reads the values the memory should end up holding, decides whether reaching that state is possible, and prints the answer.

The input describes between $1$ and $10$ target memory configurations. The first line holds a single integer, the number of configurations. Each configuration then spans two lines. The first holds an integer $l_i$ ($1 \le l_i \le 100000$), the memory size of the $i$-th configuration. The second holds a string of length $l_i$ over the letters $a$, $b$, $c$, describing the configuration you want to reach.

Print one line per configuration. For the $i$-th configuration print TAK if the initialization is possible, and NIE otherwise.