令 $h$ 为一个作用于由数字 0 和 1 组成的字符串上的函数。函数 $h$ 通过（独立且同时地）将每个数字 0 替换为 1，并将每个数字 1 替换为字符串 “10” 来变换字符串 $w$。例如 $h(“\texttt{1001}”)=“\texttt{101110}”$，$h(“”)=“”$（即 $h$ 将空字符串映射为空字符串）。注意 $h$ 是一个单射函数，即一一对应函数。我们用 $h_k$ 表示函数 $h$ 与自身复合 $k$ 次的结果。特别地，$h_0$ 是恒等函数 $h_0(w)=w$。

我们关注形式为 $h_k(“\texttt{0}”)$ 的字符串，其中 $k=0,1,2,3,…$。该序列以以下字符串开头：

$$“\texttt{0}”, “\texttt{1}”, “\texttt{10}”, “\texttt{101}”, “\texttt{10110}”, “\texttt{10110101}”$$

如果字符串 $x$ 在字符串 $y$ 中作为连续（即一块）子序列出现，则称 $x$ 是 $y$ 的子串。给定一个整数序列 $k_1,k_2,…,k_n$。你的任务是检查形式为 $h_{k_1}(“\texttt{0}”)⋅h_{k_2}(“\texttt{0}”)⋅⋅⋅h_{k_n}(“\texttt{0}”)$ 的字符串是否为某个 $h_m(“\texttt{0}”)$ 的子串，如果是，请找出满足条件的最小 $m$。

输入格式

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

输出格式

你的程序应向标准输出打印 $t$ 行，每个测试单元一行。对应于每个测试单元的行应包含一个单词：TAK（波兰语中的“是”，如果 $h_{k_1}(“\texttt{0}”)⋅h_{k_2}(“\texttt{0}”)⋅⋅⋅h_{k_n}(“\texttt{0}”)$ 是某个 $h_m(“\texttt{0}”)$ 的子串），否则输出 NIE（波兰语中的“否”）。

样例

输入 1

2
2
1 2
2
2 0

输出 1

TAK
NIE

说明 1

第一个测试用例中的字符串是 $“\texttt{110}”$ —— 它是 $h_4(“\texttt{0}”)=“\texttt{10110}”$ 的子串。在第二个测试单元中，字符串为 $“\texttt{100}”$，它不是任何 $h_m(“\texttt{0}”)$ 的子串。