在 Bajtosia 的幼儿园里有很多玩具，小女孩有时很难决定当天要玩哪一个。为了方便选择，Bajtosia 决定使用数数游戏（即“点兵点将”）。

如果某天她想从 $n$ 个玩具中选出一个，她会将它们排成一排，并从 $1$ 到 $n$ 进行编号。她先指向其中一个玩具，然后开始念数数歌，每念一个音节，就移动到当前玩具的前一个或后一个玩具（对于第 $1$ 个和第 $n$ 个玩具，她没有选择，必须分别移动到 $2$ 和 $n-1$）。最后指向的玩具就是她当天要玩的玩具。

在数数过程中，Bajtosia 会记录每个玩具被指到的次数：数数结束后，第 $i$ 个玩具被指到了 $a_i$ 次。请检查 Bajtosia 是否记错了，即对于她记录的序列 $a_1, a_2, \dots, a_n$，判断是否存在一种符合该序列的数数过程。

这种情况在 $t$ 天内重复发生，每天的玩具子集和数数歌都可能不同。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)，表示 Bajtosia 使用数数游戏选择玩具的天数。接下来是 $t$ 个描述，依次对应每一天。

每天描述的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示当天参与数数游戏的玩具数量。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示根据 Bajtosia 的记录，各个玩具被指到的次数。

你可以假设至少有一个 $a_i$ 不为零。

所有天数中 $n$ 的总和不超过 $1\,000\,000$。

输出格式

输出 $t$ 行，每行包含一个单词 TAK 或 NIE。TAK 表示存在符合 Bajtosia 记录的数数过程，NIE 表示不存在。

样例

输入 1

7
3
1 3 1
2
5 7
3
0 1 0
1
2
6
3 3 2 1 0 0
5
1 3 2 2 3
3
1 0 1

输出 1

TAK
NIE
TAK
NIE
TAK
NIE
NIE

说明 1

第一天，Bajtosia 在数数过程中可能依次指到了玩具 2, 1, 2, 3, 2。 第三天，她使用了简短的数数歌，并开始玩第一个被指到的玩具。 第五天，她可能依次指到了玩具 1, 2, 3, 4, 3, 2, 1, 2, 1。 对于其余的天数，不存在对应的数数过程。