Johny 和 Margaret 正在玩“鹅卵石”游戏。桌上最初有一些鹅卵石，被分成了 $n$ 堆。这些堆并排排列成一行。鹅卵石的排列满足一个附加属性：每一堆的鹅卵石数量都不少于其左侧的那一堆（最左侧的一堆除外）。玩家轮流从自己选择的某一堆中移除任意数量的鹅卵石。但他们必须注意，不能使任何一堆的鹅卵石数量少于其左侧的那一堆。换句话说，移动后这些堆必须仍然满足初始属性。当一名玩家无法进行移动时（即在他移动前桌上已经没有鹅卵石了），他就输了。为了弥补 Margaret 在这个游戏中的精湛技艺，Johny 总是先手。

事实上，Margaret 非常厉害，她总是能做出最优决策，只要有机会就会赢得比赛。因此，Johny 向你寻求帮助——他想知道在特定的初始排列下，他是否有机会击败 Margaret。请编写一个程序来回答 Johny 的询问。

标准输入的第一行包含一个整数 $u$ ($1 \le u \le 10$)，表示需要分析的初始鹅卵石排列数量。接下来的 $2u$ 行包含这些排列的描述；每个排列占用两行。

每个描述的第一行包含一个整数 $n$ ($1 \le n \le 1\,000$)，表示堆的数量。描述的第二行包含 $n$ 个非负整数 $a_i$，由空格分隔，表示从左到右各堆中鹅卵石的数量。这些数字满足以下不等式 $a_1 \le a_2 \le \dots \le a_n$。任何排列中鹅卵石的总数不超过 10,000。

标准输出应精确打印 $u$ 行。第 $i$ 行（对于 $1 \le i \le u$）应输出 TAK（波兰语中的“是”），如果 Johny 在给定的第 $i$ 个初始排列中先手可以获胜；或者输出 NIE（波兰语中的“否”），如果假设 Margaret 采取最优策略，Johny 必输无疑。

样例

输入 1

2
2
2 2
3
1 2 4

输出 1

NIE
TAK