【bzoj1115】[POI2009]石子游戏Kam

2014年5月13日2,0060

Description

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

Input

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

Output

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

Sample Input

2
2
2 2
3
1 2 4

Sample Output

NIE
TAK

题解