단어

$h$는 숫자 0과 1로 이루어진 이진 문자열에 작용하는 함수입니다. 이 함수는 문자열의 모든 0을 1로, 모든 1을 10으로 동시에 그리고 서로 독립적으로 바꿉니다. 예를 들어 $h$는 1001을 101110으로 보내고, 빈 문자열은 빈 문자열로 보냅니다. $h$는 단사(일대일) 함수입니다.

$h^k$는 $h$를 $k$번 합성한 함수를 뜻하며, $h^0$은 항등함수입니다 ($h^0(w) = w$).

$k = 0, 1, 2, \ldots$에 대한 문자열 $h^k(\texttt{0})$을 생각합니다. 처음 몇 개는 다음과 같습니다.

0, 1, 10, 101, 10110, 10110101

문자열 $x$가 문자열 $y$ 안에 연속된 한 덩어리로 나타나면 $x$를 $y$의 부분 문자열이라고 합니다. 정수 $k_1, k_2, \ldots, k_n$이 주어집니다. 다음과 같이 이어 붙인 문자열

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

이 어떤 $m \ge 0$에 대한 $h^m(\texttt{0})$의 부분 문자열인지 판정하세요.

첫 번째 줄에 시험 단위의 개수를 나타내는 정수 $t$ ($1 \le t \le 13$)가 주어집니다.

각 시험 단위는 두 줄로 이루어집니다. 첫 줄에는 정수 $n$ ($1 \le n \le 100000$)이, 둘째 줄에는 공백 하나로 구분된 $n$개의 음이 아닌 정수 $k_1, k_2, \ldots, k_n$이 주어집니다. 이 둘째 줄에 있는 정수들의 합은 $10000000$을 넘지 않습니다.

각 시험 단위마다 한 줄씩, 모두 $t$개의 줄을 출력합니다. 이어 붙인 문자열 $h^{k_1}(\texttt{0}) \cdots h^{k_n}(\texttt{0})$이 어떤 $m$에 대한 $h^m(\texttt{0})$의 부분 문자열이면 TAK을, 그렇지 않으면 NIE를 출력합니다. (TAK과 NIE는 각각 폴란드어로 예와 아니요를 뜻합니다.)

$k = (1, 2)$인 경우 문자열은 1 다음에 10, 즉 110이고, 110은 $h^4(\texttt{0}) = \texttt{10110}$의 부분 문자열이므로 답은 TAK입니다.

$k = (2, 0)$인 경우 문자열은 10 다음에 0, 즉 100입니다. 00은 어떤 $h^m(\texttt{0})$에도 나타나지 않으므로 100은 부분 문자열이 될 수 없고 답은 NIE입니다.