EOJ Test Round #1

C. 多边形游戏

单点时限: 2.0 sec

内存限制: 256 MB

两个玩家玩多边形游戏。一个凸 (n) 边形可以被 (n-3) 条对角线分成 (n-2) 个三角形,当然这些对角线可能交于多边形的一个顶点。其中某一个三角形涂成黑色,其它为白色。两个玩家轮流剪三角形,当然每次只能剪靠边的一个(即只能沿某条对角线剪一刀)。最后谁剪到黑色三角形谁就赢。(注:所谓凸多边形是指这个多边形的任意一条对角线都在多边形的内部。)

编一程序读入对多边形的描述,判断先剪的玩家是否会赢。

输入格式

第一行为一个自然数 (k) ((k \leq 5)),表示测试数据的组数,接下来是连续的 (k) 组测试数据,相邻两组测试数据之间没有空行。每组测试数据的第一行为一个整数 (n) ((4 \leq n \leq 50000)) 表示多边形的顶点数。且多边形的顶点按顺时针编号为 (0) 至 (n-1),紧接着的 (n-2) 行每行为由空格分开的 3 个非负整数,表示三角形的三个顶点。其中第一个三角形为黑色。

输出格式

共 (k) 行,每行为一个单词 TAK (表明先剪的人有必胜策略) 或 NIE (表明先剪的人无必胜策略)。

样例

Input
1
6
0 1 2
2 4 3
4 2 0
0 5 4
Output
TAK