Words

Let $h$ be a function on binary strings (strings of the digits 0 and 1). It rewrites a string by replacing, simultaneously and independently, every 0 with 1 and every 1 with 10. For instance $h$ sends 1001 to 101110, and it sends the empty string to the empty string. The map $h$ is injective (one to one).

Let $h^k$ denote $h$ applied $k$ times, with $h^0$ the identity ($h^0(w) = w$).

Consider the strings $h^k(\texttt{0})$ for $k = 0, 1, 2, \ldots$ The first few are:

0, 1, 10, 101, 10110, 10110101

A string $x$ is a substring of a string $y$ when it appears in $y$ as one contiguous block. You are given integers $k_1, k_2, \ldots, k_n$. Concatenate

$h^{k_1}(\texttt{0})\, h^{k_2}(\texttt{0}) \cdots h^{k_n}(\texttt{0})$

and decide whether the resulting string is a substring of $h^m(\texttt{0})$ for some $m \ge 0$.

The first line holds an integer $t$ ($1 \le t \le 13$), the number of test units.

Each test unit uses two lines. The first line holds an integer $n$ ($1 \le n \le 100000$). The second line holds $n$ non-negative integers $k_1, k_2, \ldots, k_n$ separated by single spaces. The sum of the integers on that second line is at most $10000000$.

Print $t$ lines, one per test unit. For a test unit print TAK if the concatenation $h^{k_1}(\texttt{0}) \cdots h^{k_n}(\texttt{0})$ is a substring of $h^m(\texttt{0})$ for some $m$, and NIE otherwise. (TAK and NIE are Polish for yes and no.)

Take $k = (1, 2)$: the string is 1 followed by 10, that is 110, and 110 is a substring of $h^4(\texttt{0}) = \texttt{10110}$, so the answer is TAK.

Take $k = (2, 0)$: the string is 10 followed by 0, that is 100. The block 00 never occurs in any $h^m(\texttt{0})$, so 100 cannot be a substring and the answer is NIE.