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
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define bitcountll(x) __builtin_popcountll(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define eb emplace_back
//~ #define r(x) resize(x)
//~ #define rf(x, c) resize(x, c)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
//~ void read(int &a){
		//~ a = 0; char c = _getchar_nolock();
		//~ while(c<'0'||'9'<c) c = _getchar_nolock();
		//~ while('0'<=c&&c<='9') a = a*10+c-'0', c = _getchar_nolock();
//~ }
int inf = 2.1e09; ll infll = 2e18; int mod = (1<<23)*119+1; //1e09+7;
bool answer(){
	int n; scanf("%d", &n);
	V<int> t(n+1, 0);
	for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);

	int fst = 0, lst = 0;
	for(int i = 1; i <= n; ++i) if(t[i])
		fst = fst ? fst : i, lst = i;
	for(int i = fst; i <= lst; ++i)
		if(!t[i]) return 0;
	if(fst == lst)
		return t[fst] == 1;
	
	V<V<ll>> x(3);
    x[0].emplace_back(t[fst]*2);
    x[1].emplace_back(t[fst]*2-1);
	if(t[fst] >= 2)
        x[2].emplace_back(t[fst]*2-2);

	for(int i = fst+1; i <= lst; ++i){
        V<V<ll>> y(3);
		for(int j = 2; ~j; --j)
            for(ll u : x[j]){
                ll v = (t[i]-(u+1)/2)*2 + (u&1);
                if(v < 0 || (!v && i != lst))
                    continue;
                y[j].emplace_back(v);
                for(int l = 1; l < 3; ++l)
                    if(j+l < 3 && v >= l &&
                        find(all(y[j+l]), v-l) == y[j+l].end()){
                            if(v-l == 0 && i != lst) continue;
                            y[j+l].emplace_back(v-l);
                        }
		}
        x = y;
	}
	return find(all(x[2]), 0) != x[2].end();
}
int main(){
	int T = 1;
	scanf("%d", &T);
	//ios_base::sync_with_stdio(0); cin.tie(0);// cin >> T;
	for(++T; --T; ){
        bool result = answer();
        printf(result ? "TAK\n" : "NIE\n");
    }
	return 0;
}