题目描述
给出长度为 $n$ 的 01 序列 $a_{1\sim n}$，序列中有偶数个 1。NIT 和 TIN 轮流做以下操作，NIT 先手：
- 选择位置 $i\ (1\le i\le n)$，满足区间 $[1,i]$ 中有奇数个
1。再选择位置 $j\ (i\lt j\le n)$。将 $a_i,a_j$ 都取反（即，0变1，1变0）
当整个序列中的所有元素都变为 0 时，当前轮到的人就无法操作，他就输了。假设 NIT 和 TIN 都绝顶聪明，谁会赢？可以证明，游戏总会结束。
$n$ 可能很大，但序列中 $1$ 的个数不超过 $2\times 10^5$。
输入格式
本题有多组数据。
输入的第一行是数据组数 $T$。
接下来是每组数据的描述。每组数据的第一行是两个正整数 $n,m$，$m$ 为序列中 1 的个数，保证 $m$ 是偶数。
接下来一行 $m$ 个递增的正整数，描述这些 1 的下标，下标从 $1$ 开始。
输出格式
对每组数据，输出一行一个字符串 NIT 或 TIN，表示赢家的名字。
样例 #1
样例输入 #1
3 4 2 1 3 4 4 1 2 3 4 10 4 1 3 7 8
样例输出 #1
NIT TIN NIT
提示
样例解释
第一组数据中，NIT 选择 $i=1,j=3$ 就能把全部位置都变成 0，使得 TIN 无法操作。
第二组数据中，无论 NIT 先手怎么操作，都会剩下恰好两个 1 的位置。TIN 只需要选择这两个剩下的位置，就可以把全部位置都变成 0。
第三组数据中，一种可能的游戏进程如下（注意该进程里，每一步不一定是最优的）：
- NIT 选择 $i=2,j=3$ 并将这两个位置取反。现在
1的位置在 $1,2,7,8$。 - TIN 选择 $i=7,j=9$ 并将这两个位置取反。现在
1的位置在 $1,2,8,9$。 - NIT 选择 $i=1,j=5$ 并将这两个位置取反。现在
1的位置在 $2,5,8,9$。 - TIN 选择 $i=3,j=4$ 并将这两个位置取反。现在
1的位置在 $2,3,4,5,8,9$。 - NIT 选择 $i=4,j=5$ 并将这两个位置取反。现在
1的位置在 $2,3,8,9$。 - TIN 选择 $i=2,j=9$ 并将这两个位置取反。现在
1的位置在 $3,8$。 - NIT 选择 $i=3,j=8$ 并将这两个位置取反。现在序列里没有
1了。 - TIN 无法操作，NIT 获胜。
数据范围
对于所有数据，$1\le T\le 10^4$，$1\le n\le 10^{18}$，$2\le m\le 2\times 10^5$，$\sum m\le 10^6$。保证 $m$ 是偶数，保证为 1 的下标是递增顺序给出的。
- 子任务 1（$1$ 分）$T\le 10^3$，$n\le 10$。
- 子任务 2（$9$ 分）序列中全是
1。 - 子任务 3（$40$ 分）$T\le 100$，$n\le 100$。
- 子任务 4（$10$ 分）$\sum n\le 10^6$。
- 子任务 5（$40$ 分）没有任何附加限制。