题目描述

题目译自 XVI OI Olimpiada Informatyczna – III etap Słowa

设 $h$ 为定义在由数字 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串上的函数。函数 $h$ 将字符串 $w$ 转换为新字符串，规则为：同时且独立地将每个 $\texttt{0}$ 替换为 $\texttt{1}$，每个 $\texttt{1}$ 替换为字符串 $\texttt{10}$。例如，$h(\texttt{1001}) = \texttt{101110}$，$h(\texttt{""}) = \texttt{""}$（即空字符串映射为空字符串）。显然，$h$ 是一一映射。记 $h^k$ 为函数 $h$ 与自身 $k$ 次复合，特别地，$h^0$ 为恒等函数，即 $h^0(w) = w$。

我们关注形如 $h^k(\texttt{0})$ 的字符串，其中 $k = 0, 1, 2, 3, \ldots$。以下是前几个字符串：
$\texttt{0}$, $\texttt{1}$, $\texttt{10}$, $\texttt{101}$, $\texttt{10110}$, $\texttt{10110101}$。

若字符串 $x$ 是 $y$ 的子串，则 $x$ 作为 $y$ 的连续子序列出现。给定自然数序列 $k_1, k_2, \ldots, k_n$，任务是判断字符串

[ h^{k_1}(\texttt{0}) \cdot h^{k_2}(\texttt{0}) \cdot \ldots \cdot h^{k_n}(\texttt{0}) ]

是否为某个 $h^m(\texttt{0})$ 的子串，其中 $\cdot$ 表示字符串拼接（连接）。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 13$)，表示测试数据组数。

每组测试数据包含：

• 第一行：一个整数 $n$ ($1 \leq n \leq 100000$)。
• 第二行：$n$ 个非负整数 $k_1, k_2, \ldots, k_n$，用单空格分隔。每组测试数据中第二行数字之和不超过 $10000000$。

输出格式

输出 $t$ 行，每行对应一组测试数据，若 $h^{k_1}(\texttt{0}) \cdot h^{k_2}(\texttt{0}) \cdot \ldots \cdot h^{k_n}(\texttt{0})$ 是某个 $h^m(\texttt{0})$ 的子串，输出 $\texttt{TAK}$，否则输出 $\texttt{NIE}$。

样例

输入

2
2
1 2
2
2 0

输出

TAK
NIE

解释：

• 第一组测试数据的字符串为 $\texttt{110}$（$h^1(\texttt{0}) = \texttt{1}$, $h^2(\texttt{0}) = \texttt{10}$，拼接得 $\texttt{110}$），它是 $h^4(\texttt{0}) = \texttt{10110}$ 的子串。
• 第二组测试数据的字符串为 $\texttt{100}$（$h^2(\texttt{0}) = \texttt{10}$, $h^0(\texttt{0}) = \texttt{0}$，拼接得 $\texttt{100}$），它不是任何 $h^m(\texttt{0})$ 的子串。