Description

有 $n$ 堆石子。除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作。每次操作可以从一堆石子中移走任意多颗石子，但是要保证操作后仍然满足初始时的条件。没有石子可移动的人就输掉了游戏。问先手是否必胜。

Input Format

多组输入，第一行一个整数 $u$ 代表数据组数（$1\le u\le 10$）

接下来共 $2u$ 行，每两行代表一组数据：

第一行只有一个整数 $n$（$1\le n\le 1000$），表示石子堆数；

第二行有 $n$ 个整数用空格隔开，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆的石子个数，保证 $a_1\le a_2\le a_3\le \cdots\le a_n$。

对于每组数据，保证石子总数不超过 $1000$。

Output Format

输出 $u$ 行。在第 $i$ 行，如果第 $i$ 组数据是先手必胜，输出 TAK，否则输出 NIE。

2
2
2 2
3
1 2 4

NIE
TAK