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
90
91
#include <bits/stdc++.h>

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define f first
#define s second
#define vec vector
#define pb push_back
#define ir(a, b, x) (((a) <= (x)) && ((x) <= (b)))

using namespace std;

const int N = 1e6+100;
int n;
int l, r;

int arr[N];

int mem[N][3][5];

bool dp(int id, int offsets_left, int even_offset) {
	if (mem[id][offsets_left][2+even_offset] != -1) return mem[id][offsets_left][2+even_offset];

	int mult = 1 - 2*(id&1);
	int current_val = arr[id] + mult*even_offset;
	if (current_val <= 0 && id != l && id != r){
		mem[id][offsets_left][2+even_offset] = false;
		return mem[id][offsets_left][2+even_offset];
	}

	if (id == r) {
		if (current_val < 0) {
			mem[id][offsets_left][2+even_offset] = false;
			return mem[id][offsets_left][2+even_offset];
		}
		mem[id][offsets_left][2+even_offset] = (current_val <= offsets_left);
		return mem[id][offsets_left][2+even_offset];
	}
	
	bool output = false;
	output = output | dp(id+1, offsets_left, even_offset);
	
	if (offsets_left == 0) goto skip;
	if (current_val>1 || (current_val==1 && id==l)) 
		output = output | dp(id+1, offsets_left-1, even_offset-mult);
		
	if(offsets_left == 1) goto skip;
	if (current_val>2 || (current_val==2 && id==l)) 
			output = output | dp(id+1, offsets_left-2, even_offset-2*mult);

	skip:

	mem[id][offsets_left][2+even_offset] = output;
	return mem[id][offsets_left][2+even_offset];
}

bool solve(){
	cin >> n;

	foru(i, n) cin >> arr[i];

	l = 0;
	while(arr[l] == 0) l++;

	r = n-1;
	while(arr[r] == 0) r--;

	if (l == r && arr[l] == 1) return true;

	fors(i, r+1, l) arr[i] *= 2;

	fors(i, r, l) arr[i+1] -= arr[i];

	foru(i, n) foru(j, 3) foru(k, 5) mem[i][j][k] = -1;

	return dp(l, 2, 0);
}

int main() {
	// cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int t; cin >> t;
	foru(_i, t){
		if (solve()){
			cout << "TAK" << endl;
		} else {
			cout << "NIE" << endl;
		}
	}
    return 0;
}