시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB2000.000%

문제

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(,,1001”)=,,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, h0 is the identity function h0(w)=w.

We are interested in the strings of the form hk(,,0”) for k=0,1,2,3,… This sequence begins with the following strings:

,,0”, ,,1”, ,,10”, ,,101”, ,,10110”, ,,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 k1,k2,…,kn is given. Your task is to check whether a string of the form hk1(,,0”)⋅hk2(,,0”)⋅⋅⋅hkn(,,0”) is a substring of hm(,,0”) for some m, and if it is, you shuold find minimal such m.

입력

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 k1,k2,…,kn, separated by single spaces. The sum of the numbers in the second line of any test unit description does not exceed 10,000,000.

출력

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 hk1(,,0”)⋅hk2(,,0”)⋅⋅⋅hkn(,,0”) is a substring of  hm(,,0”) for some  in that test unit, or NIE (no in Polish) otherwise.

예제 입력 1

2
2
1 2
2
2 0

예제 출력 1

TAK
NIE

힌트

The string from the first test case is ,,110” - it is a substring of h4(,,0”)=,,10110”. In the second test unit there is a string ,,100”, which is not a substring of hm(,,0”) for any m.