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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys

def test_path(path,n,final_array):

    if len(path) == 1:
        return True

    for i in range(0, len(path)-1):
        if int(path[i]) == 1 and int(path[i+1]) != 2:
            return False

        elif int(path[i]) == n and int(path[i+1]) != n-1:
            return False

        elif int(path[i]) != 1 and int(path[i]) != n and int(path[i]) != int(path[i+1]) -1 and int(path[i]) != int(path[i+1]) +1:
            return False
        

    return True


def next_lex_perm(path):

    for i in reversed(range(0, len(path) - 1)):
        if path[i] < path[i + 1]:
            break 
    else:
        return False 

    j = next(j for j in reversed(range(i + 1, len(path))) if path[i] < path[j])

    path[i], path[j] = path[j], path[i]

    path[i + 1:] = reversed(path[i + 1:])

    return path


t = int(input())
resp_arr = []

n_array = []
command_array = []

for x in range(0, t):
    n_array.append(int(input()))
    command_array.append(input())

for x in range(0, t):

    path_array = []

    n = n_array[x]
    command = command_array[x].split(" ")

    for y in range(0,n):
        path_array.extend(int(command[y])*str(y+1))
    

    next_perm = True
    found = False
    new_array = path_array
    
    while next_perm:

        if new_array:
            if test_path(new_array,n,command):
                resp_arr.append('TAK')
                found = True
                break

        else:
            next_perm = False

        new_array = next_lex_perm(path_array)
    
    if not found:
         resp_arr.append('NIE')

print("\n".join(resp_arr))