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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
typedef pair <LL,LL> pll;
#define pb push_back
const int INF = 2147483647;
const int N = 1000005;

int tab[N], z, i, n, bat[N], ok, jed, u, st;
LL s[2];
VI v;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> z;
while (z--) {
	cin >> n;
	s[0] = s[1] = 0;
	for (i=0;i<n;i++) {
		cin >> tab[i];
		s[i % 2] += tab[i];
	}
	if (n == 1) {
		if (tab[0] != 1) cout << "NIE\n"; else cout << "TAK\n";
		continue;
	}
	i = 0;
	while (tab[i] == 0) i++;
	while (i < n && tab[i] != 0) i++;
	while (i < n && tab[i] == 0) i++;
	if (i < n) {
		cout << "NIE\n";
		continue;
	}
	if (s[0] + s[1] == 1) {
		cout << "TAK\n";
		continue;
	}
	if (max(s[0], s[1]) - min(s[0], s[1]) > 1) {
		cout << "NIE\n";
		continue;
	}
	v.clear();
	ok = 1;
	for (i=0;i<n;i++) {
		if (tab[i] == 0) continue;
		u = (i == 0 ? 0 : tab[i - 1]) + (i == n - 1 ? 0 : tab[i + 1]);
		if (tab[i] == u) v.pb(i); else if (tab[i] == u + 1) {
			v.pb(i);
			v.pb(i);
		} else if (tab[i] > u + 1) ok = 0;
	}
	if (v.size() > 2) ok = 0; else if (v.size() == 2) {
		if (s[0] > s[1] && (v[0] % 2 != 0 || v[1] % 2 != 0)) ok = 0;
		if (s[1] > s[0] && (v[0] % 2 != 1 || v[1] % 2 != 1)) ok = 0;
		if (s[1] == s[0] && v[0] % 2 == v[1] % 2) ok = 0;
	} else if (v.size() == 1) {
		if (s[0] > s[1] && v[0] % 2 == 1) ok = 0;
		if (s[1] > s[0] && v[0] % 2 == 0) ok = 0;
	}
	if (!ok) cout << "NIE\n"; else cout << "TAK\n";
}
return 0;
}