In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
For the input data:
2 2 1 2 2 2 0
the correct result is:
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.