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
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
using ll = long long;

void solve(){
	int n;
	cin>>n;
	deque<ll> q(n);
	for(int i=0; i<n; i++){
		cin>>q[i];
	}
	while(q.size() && !q.front()) q.pop_front();
	while(q.size() && !q.back()) q.pop_back();
	n = q.size();
	if(n <= 1){
		if(!n || q[0] == 1){
			cout<<"TAK"<<nl;
		}else{
			cout<<"NIE"<<nl;
		}
		return;
	}
	vector<ll> indeg(n-1), outdeg(n-1);
	int p = -1, k = -1;
	indeg[0] = outdeg[0] = q[0];
	for(int i=1; i<n-1; i++){
		indeg[i] = q[i] - outdeg[i-1];
		outdeg[i] = q[i] - indeg[i-1];
		if(indeg[i] < -1 || outdeg[i] < 0){
			cout<<"NIE"<<nl;
			return;
		}
		if(outdeg[i] == 0){
			if(p != -1){
				cout<<"NIE"<<nl;
				return;
			}
			p = i-1;
			//cerr<<"P: "<<p<<nl;
			indeg[i-1]--;
			outdeg[i]++;
		}
		if(indeg[i] == -1){
			//cerr<<"AAAAAAA"<<nl;
			assert(0);
		}
	}
	if(p == -1 && indeg[n-2] == q[n-1]+1){
		p = n-2;
		//cerr<<"P: "<<p<<nl;
		indeg[n-2]--;
	}
	if(p == -1 && outdeg[n-2] == q[n-1]-1){
		p = n-1;
		//cerr<<"P: "<<p<<nl;
		outdeg[n-2]++;
	}
	if(indeg[n-2] == q[n-1] && outdeg[n-2] == q[n-1]+1){
		k = n-2;
		//cerr<<"K: "<<k<<nl;
		outdeg[n-2]--;
		cout<<"TAK"<<nl;
		return;
	}
	if(indeg[n-2] == q[n-1]-1 && outdeg[n-2] == q[n-1]){
		k = n-1;
		//cerr<<"K: "<<k<<nl;
		indeg[n-2]++;
		cout<<"TAK"<<nl;
		return;
	}
	if(indeg[n-2] == q[n-1] && outdeg[n-2] == q[n-1]){
		cout<<"TAK"<<nl;
	}else{
		cout<<"NIE"<<nl;
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}