Pebbles

Johny and Margaret play a game called "pebbles". Some pebbles sit on a table, grouped into $n$ piles placed next to each other in a single row. The arrangement always satisfies one extra property: every pile holds at least as many pebbles as the pile immediately to its left (the leftmost pile is the obvious exception).

The players take turns. On a turn, a player removes any positive number of pebbles from a single pile of their choice. They must be careful, though: after the move the piles must still be non-decreasing from left to right, so no pile may become smaller than the pile to its left. A player who cannot move (there are no pebbles on the table when their turn begins) loses. Johny always moves first, to compensate for Margaret's mastery of this game.

Margaret is so good that she always plays the best move and wins whenever she gets the chance. Johny therefore asks for your help: he wants to know whether he has any chance of beating Margaret from a given initial arrangement. Write a program that answers Johny's questions.

The first line contains a single integer $u$ ($1 \le u \le 10$), the number of initial arrangements to analyse. The next $2u$ lines describe these arrangements, two lines each.

The first line of a description contains a single integer $n$ ($1 \le n \le 1000$), the number of piles. The second line contains $n$ non-negative integers $a_i$ separated by single spaces, the pebble counts of the successive piles from left to right; they satisfy $a_1 \le a_2 \le \dots \le a_n$. The total number of pebbles in any arrangement does not exceed 10000.

Print exactly $u$ lines. Assuming both players play optimally, line $i$ holds TAK if Johny can win starting from the $i$-th arrangement, or NIE if he is bound to lose. TAK and NIE are the exact strings you must print.