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
import os,io,sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
def test(a,p):
	#print('#',p,a)
	if p==1:
		if a[0]>a[1]:
			return False
		elif a[0]==a[1]:
			p = 2
		else:
			a[1] -= a[0]
	while p<len(a)-1:
		if p==len(a)-2:
			return a[p]-a[p+1] in [0,1]
		if a[p]>a[p+1]: return False
		a[p+1]-= a[p]-1
		p += 1
	
def solve(n,a):
	p = 0
	while a[p]==0: p +=1
	k = n-1
	while a[k]==0: k -= 1
	a = a[p:k+1]
	if len(a)==1: return a[0]==1
	if 0 in a: return False
	s0,s1 = sum(a[0::2]), sum(a[1::2])
	#print(a,s0,s1)
	if abs(s1-s0)>1: return False
	if len(a)==2: return True
	if s1==s0:
		return test(a[:],0) or test(a,1)
	p = 0
	if s1>s0:
		if a[0]>a[1]:
			return False
		elif a[0]==a[1]:
			p = 2
		else:
			a[1] -= a[0]
			p = 1 
	#print('+',a)
	while p<len(a)-1:
		if p==len(a)-2:
			return a[p]-a[p+1] in [0,1]
		if a[p]>a[p+1]: return False
		a[p+1]-= a[p]-1
		p += 1
		
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int,input().split()))
	ans.append("TAK" if solve(n,a) else "NIE")
print("\n".join(ans))