#1115. [POI2009]石子游戏Kam

内存限制:162 MiB 时间限制:10 Sec

题目描述

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

输入格式

第一行u表示数据组数。对于每组数据,第一行N表示石子堆数,第二行N个数ai表示第i堆石子的个数(a1<=a2<=……<=an)。 1<=u<=10 1<=n<=1000 0<=ai<=10000

输出格式

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

样例

样例输入


			
2
2
2 2
3
1 2 4

样例输出


			
NIE
TAK

数据范围与提示

感谢MT大牛翻译.