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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
#define st first
#define nd second
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define pu push
#define pub push_back
#define pob pop_back
#define em emplace
#define emb emplace_back

ll n;
vc<ll> a;

void input() {
	cin >> n;
	a.resize(n);
	for (ll &ai : a)
		cin >> ai;
}

void tran(ll i, ll j, ll k, vc<set<ll>> &tmp) {
	ll z = max(0ll, (k - (j == 0) - (j + k == 0)) / 2);
	if (k - z > a[i])
		return;
	tmp[j].insert(-k + 2 * a[i]);
}

bool solve() {
	while (a.back() == 0)
		a.pob();
	reverse(all(a));
	while (a.back() == 0)
		a.pob();
	reverse(all(a));
	n = sz(a);

	vc<set<ll>> dp(2);
	dp[0].insert(0);
	for (ll i = 0; i < n; i++) {
		vc<set<ll>> tmp(2);
		for (ll j = 0; j < 2; j++)
			for (ll k : dp[j]) {
				tran(i, j, k, tmp);
				if (j == 0)
					tran(i, 1, k + 1, tmp);
				if ((j + k) % 2 == 0)
					tran(i, j, k + 1, tmp);
				if (j == 0 and (j + k) % 2 == 0)
					tran(i, 1, k + 2, tmp);
			}
		if (i + 1 < n) {
			tmp[0].erase(0);
			tmp[1].erase(0);
		}
		swap(dp, tmp);
	}
	return dp[1].find(0) != dp[1].end();
}

void program() {
	input();
	if (solve())
		cout << "TAK\n";
	else
		cout << "NIE\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll T = 1;
	cin >> T;
	while (T--) {
		program();
	}
	return 0;
}