描述

有 $n$ 堆石子，个数单调不降。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足石子数量单调不降。

谁没有石子可移时输掉游戏。问先手是否必胜。

输入格式

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

对于每组数据，第一行 $n$ 表示石子堆数，第二行 $n$ 个数 $a_i$ 表示第 $i$ 堆石子的个数

输出格式

$u$ 行，若先手必胜输出 TAK，否则输出 NIE。

2
2
2 2
3
1 2 4

NIE
TAK

范围

$1\le u\le10,1\le n\le 1000,0\le a_1\le a_2\le\cdots\le a_n\le10^4$