Let $h$ be a function acting on strings composed of the digits 0 and 1. The function h transforms the string w by replacing (independently and concurrently) every digit 0 with 1 and every digit 1 with the string ,,10”. For example $h(“\texttt{1001}”)=“\texttt{101110}”$, $h(“”)=“”$ (i.e. $h$ assigns an empty string to the empty string). Note that $h$ is an injection, or a one-to-one function. By $h_k$ we denote the function $h$ composed with itself $k$ times. In particular, $h_0$ is the identity function h0(w)=w.

We are interested in the strings of the form $h_k(“\texttt{0}”)$ for $k=0,1,2,3,…$ This sequence begins with the following strings:

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

We call the string $x$ a substring of the string $y$ if it occurs in $y$ as a contiguous (i.e. one-block) subsequence. A sequence of integers $k_1,k_2,…,k_n$ is given. Your task is to check whether a string of the form $h_{k_1}(“\texttt{0}”)⋅h_{k_2}(“\texttt{0}”)⋅⋅⋅h_{k_n}(“\texttt{0}”)$ is a substring of $h_m(“\texttt{0}”)$ for some $m$, and if it is, you shuold find minimal such $m$.

Input

The first line of the standard input contains a single integer $t$, $1 ≤ t ≤ 13$, denoting the number of test units. The first line of each test unit's description contains one integer $n$, $1 ≤ n ≤ 100\,000$. The second line of each description holds $n$ non-negative integers $k_1,k_2,…,k_n$, separated by single spaces. The sum of the numbers in the second line of any test unit description does not exceed $10\,000\,000$.

Output

Your programme should print out t 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 $h_{k_1}(“\texttt{0}”)⋅h_{k_2}(“\texttt{0}”)⋅⋅⋅h_{k_n}(“\texttt{0}”)$ is a substring of $h_m(“\texttt{0}”)$ for some in that test unit, or NIE (no in Polish) otherwise.

Example

Input

2
2
1 2
2
2 0

Output

TAK
NIE

The string from the first test case is $“\texttt{110}”$ - it is a substring of $h_4(“\texttt{0}”)=“\texttt{10110}”$. In the second test unit there is a string $“\texttt{100}”$, which is not a substring of $h_m(“\texttt{0}”)$ for any $m$.