题目描述

题目译自 XVI OI Olimpiada Informatyczna – I etap Kamyki

Jaś 和 Małgosia 正在玩一场名为「鹅卵石」的游戏。游戏开始时，桌上摆放着若干鹅卵石，分成 $n$ 堆，依次排列成一行。鹅卵石堆满足特定条件：每堆鹅卵石数量不少于其左侧相邻堆（第一堆左侧无堆，例外）。两人轮流从任意一堆中移除正数个鹅卵石，但需保证该堆剩余鹅卵石数不少于左侧相邻堆，保持初始排列的性质。无法移除鹅卵石的一方（即轮到其操作时桌上无鹅卵石）输掉游戏。Jaś 总是先手。

Małgosia 擅长此游戏，若有机会必会选择必胜策略。Jaś 向你求助：他想知道，对于给定的初始鹅卵石的排列，他是否有机会战胜 Małgosia。编写程序，判断 Jaś 的胜负可能性。

输入格式

第一行包含一个整数 $u$ $(1 \leq u \leq 10)$，表示需分析的初始鹅卵石排列数量。

接下来的 $2u$ 行描述这些排列，每组排列占两行：

• 第一行包含一个整数 $n$ $(1 \leq n \leq 1000)$，表示鹅卵石堆数。
• 第二行包含 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$，表示从左到右各堆鹅卵石数量，满足 $a_1 \leq a_2 \leq \ldots \leq a_n$。

每组排列的总鹅卵石数不超过 $10000$。

输出格式

输出 $u$ 行，若 Jaś 从第 $i$ 个初始排列开始有胜算，在第 $i$ $(1 \leq i \leq u)$ 行输出 TAK；若在 Małgosia 的最优策略下 Jaś 必输，输出 NIE。

2
2
2 2
3
1 2 4

NIE
TAK