1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
from collections import deque

def read_input():
    t = int(sys.stdin.readline().strip())
    cases = []
    for _ in range(t):
        n = int(sys.stdin.readline().strip())
        data = deque(map(int, sys.stdin.readline().split()))
        cases.append(data)
    return cases

def analyse_iterative(dlist):
    while True:
        while dlist and dlist[0] == 0:
            dlist.popleft()
        while dlist and dlist[-1] == 0:
            dlist.pop()

        if len(dlist) == 1:
            return "TAK" if dlist[0] == 1 else "NIE"
        if len(dlist) == 2:
            return "TAK" if abs(dlist[0] - dlist[1]) == 1 else "NIE"

        if dlist[0] % 2 == 0:
            if dlist[-1] % 2 == 0:
                return "NIE"
            else:
                if dlist[-2] > dlist[-1]:
                    dlist[-2] -= dlist[-1]
                    dlist.pop()
                else:
                    return "NIE"
        else:
            if dlist[1] >= dlist[0]:
                dlist[1] -= dlist[0]
                dlist.popleft()
            else:
                return "NIE"

cases = read_input()
for dlist in cases:
    print(analyse_iterative(dlist))