小 Bytie 非常喜欢观看每年在 Bytetown 和 Byteburg 之间举行的 F1 比赛。对他来说，最激动人心的时刻就是超车。他希望能看到尽可能多的超车。

Bytie 梦想着一场 F1 比赛，其中有 $n$ 辆赛车参赛，且起跑位置为第 $i$ 位（对于每个 $1 \le i \le n$）的赛车在比赛中完成了 $a_i$ 次超车。为了简化问题，我们假设在任何时刻最多只会发生一次超车，且每次超车恰好涉及两辆赛车（即一辆赛车超过另一辆赛车）。

Bytie 想知道这样的比赛是否可能发生。你能帮他判断一下吗？

输入格式

输入的第一行包含一个正整数 $t$，表示测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示参赛赛车的数量。第二行包含一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) 组成的序列，表示各赛车完成的超车次数。

单个输入文件的大小不超过 20 MB。

输出格式

你的程序应输出 $t$ 行，包含对应测试用例的答案。每一行应包含一个单词 TAK（波兰语中的“是”）或 NIE（波兰语中的“否”），具体取决于测试用例描述的比赛是否可能发生。

样例

输入 1

3
2
0 1
3
0 1 4
3
1 1 3

输出 1

TAK
NIE
TAK