题目描述

Let be a function acting on strings composed of the digits 0 and 1.

The function transforms the string by replacing (independently and concurrently) every digit 0 with 1 and every digit 1 with the string .

For example , (i.e. assigns an empty string to the empty string).

Note that is an injection, or a one-to-one function.

By we denote the function composed with itself times.

In particular, is the identity function .

We are interested in the strings of the form for This sequence begins with the following strings:

, , , , , .

We call the string a substring of the string if it occurs in as a contiguous (i.e. one-block) subsequence.

A sequence of integers is given.

Your task is to check whether a string of the form is a substring of for some .

输入格式

The first line of the standard input contains a single integer , , denoting the number of test units.

The first line of each test unit's description contains one integer , .

The second line of each description holds non-negative integers , separated by single spaces.

The sum of the numbers in the second line of any test unit description does not exceed .

输出格式

Your programme should print out lines to the standard output, one for each test unit.

Each line corresponding to a test unit should contain one word:

TAK (yes in Polish - if is a substring of for some in that test unit, or NIE (no in Polish) otherwise.

题目大意

题目描述

函数 $h$ 作用于由数字 $0$ 和 $1$ 组成的字符串，其通过将每一个数字 $0$ 替换为 $1$，将每一个数字 $1$ 替换为字符串 $10$ 来独立且同时地变换字符串 $w$。

例如：

$$h(``1001")=``101110"$$ $$h(``\ ")=``\ "$$

其中例二即把空字符串赋值给空字符串。

注意， $h$ 是一个一对一的函数。

我们用 $h^k$ 表示函数 $h$ 使用 $k$ 次。

特别的， $h^0(w)=w$。

我们对 $k = 0, 1, 2, ...$ 的 $h^k(``0")$ 形式的字符串感兴趣，这个序列为:

$$``0", ``1", ``10", ``101", ``10110", ``10110101", \ldots $$

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

输入内容

输入的第一行包含一个整数 $t$ 表示样例数， $1 \leq t \leq 13$。每个样例输入两行，一行 $n$ ， $1 \leq n \leq 100000$ ，另一行为 $n$ 个非负整数 $k_1, k_2, k_3, ..., k_n$，用单个空格分隔。

输出内容

您的程序应该输出 $t$ 行，每个测试输出一行。如果存在 $m$ 使 $h^{k_1}(``0") \cdot h^{k_2}(``0") \cdot \ldots \cdot h^{k_n}(``0") $ 是 $h^m(``0")$ 的子串，就输出 TAK（波兰语中的 yes ），如果不存在 $m$，则输出 NIE（波兰语中的 no ）。

Translated By in_young_ren

2
2
1 2
2
2 0

TAK
NIE