Words

Memory limit: 64 MB

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 .

Input

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 .

Output

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.

Example

For the input data:

2
2
1 2
2
2 0

the correct result is:

TAK
NIE

Explanation of the example: The string from the first test unit is - it is a substring of for example. In the second test unit there is a string , which is not a substring of for any .

Task authors: Wojciech Rytter and Bartosz Walczak.