Description

设 $h$ 是一个作用于由数字 0 和 1 组成的字符串的函数。函数 $h$ 将字符串 $w$ 转换为：独立且同时地将每个数字 0 替换为 1，并将每个数字 1 替换为字符串 "10"。例如，$h("1001") = "101110"$，$h("") = ""$（即 $h$ 将空字符串映射为空字符串）。注意，$h$ 是一个单射，即一对一的函数。$h^k$ 表示函数 $h$ 自身复合 $k$ 次。特别地，$h^0$ 是恒等函数 $h^0(w)=w$。

我们对形如 $h^k("0")$ 的字符串感兴趣，其中 $k = 0,1,2,3,\cdots$。该序列以以下字符串开始：

"0", "1", "10", "101", "10110", "10110101"。

如果字符串 $x$ 作为一个连续（即单块）子序列出现在字符串 $y$ 中，我们称字符串 $x$ 是字符串 $y$ 的一个子串。给定一个整数序列 $k_1,k_2,\cdots,k_n$。你的任务是检查形如 $h^{k_1}("0") \cdot h^{k_2}("0") \cdots h^{k_n}("0")$ 的字符串是否是某个 $h^m("0")$ 的子串。

Input Format

标准输入的第一行包含一个整数 $t$，$1 \leq t \leq 13$，表示测试单元的数量。每个测试单元的描述的第一行包含一个整数 $n$，$1 \leq n \leq 100000$。每个描述的第二行包含 $n$ 个非负整数 $k_1,k_2,\cdots,k_n$，以单个空格分隔。任何测试单元描述的第二行中的数字之和不超过 10000000。

Output Format

你的程序应输出 $t$ 行到标准输出，每行对应一个测试单元。每个对应测试单元的行应包含一个单词：TAK（波兰语中的“是”——如果 $h^{k_1}("0") \cdot h^{k_2}("0") \cdots h^{k_n}("0")$ 是某个 $h^m("0")$ 的子串），否则为 NIE（波兰语中的“否”）。

2
2
1 2
2
2 0

TAK
NIE

Hint

题面翻译由 ChatGPT-4o 提供。