[POI2009]石子游戏Kam

有 $N$ 堆石子，第 $i$ 堆石子的数量为 $a_i$，且满足：

$$a_1\le a_2\le\cdots\le a_N。$$

两名玩家轮流操作。每次操作可以从任意一堆石子中移走任意数量的石子，但操作后各堆石子的数量仍须满足上述非递减条件。无法进行操作的玩家输掉游戏。

对于每组数据，判断先手是否必胜。

输入格式

第一行输入一个整数 $u$，表示数据组数。

对于每组数据：

• 第一行输入一个整数 $N$，表示石子堆数；
• 第二行输入 $N$ 个整数 $a_1,a_2,\ldots,a_N$，其中 $a_i$ 表示第 $i$ 堆石子的数量，并保证 $a_1\le a_2\le\cdots\le a_N$。

输出格式

对于每组数据输出一行。若先手必胜，输出 TAK；否则输出 NIE。

样例输入

2
2
2 2
3
1 2 4

样例输出

NIE
TAK

数据范围

• $1\le u\le 10$；
• $1\le N\le 1000$；
• $0\le a_i\le 10000$。

来源与许可

本题为 POI 2009 试题「石子游戏 Kam」，题面与测试数据整理自 BZOJ。

样例 1

输入

2
2
2 2
3
1 2 4

输出

NIE
TAK