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
//PROBLEM 2B
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define encode(ops, status) ((status)*2+ops)
bool solve(vector<int> a) {
    int n = a.size();
    int start = 0;
    while(start < n && a[start] == 0) start++;
    int finish = n;
    while(finish - 1 >= 0 && a[finish - 1] == 0) finish--;
    a = vector<int>(a.begin() + start, a.begin() + finish);
    n = a.size();

    array<uint8_t, 6> def; def.fill(0);
    vector<array<uint8_t, 6>> vis(n + 1, def);
    vis[0][encode(0, 0)] = 1;
    
    int par_diff = 0;
    for(int pos = 0; pos < n; pos++) {
        int base = max(0, abs(par_diff) - 1);
        par_diff += (pos%2?1:-1) * a[pos];
        int next_base = max(0, abs(par_diff) - 1);
        for(int ops = 0; ops <= 1; ops++) {
            int real_ops = base + ops;
            int pos_left = a[pos] - real_ops;
            for(int st = 0; st < 3; st++) {
                if(vis[pos][encode(ops, st)]) {
                    //cout << pos << "(" << pos_left << ") " << ops << " " << st<<endl;
                }
            }
            if(pos_left < 0) continue;
            int go_zero = pos_left - next_base;
            int go_one = pos_left - 1 - next_base;
            //cout << go_one << "go" <<endl;
            //state = 0
            //turn into 0
            if(vis[pos][encode(ops, 0)] & (go_zero == (go_zero & 1))) {
                vis[pos + 1][encode(go_zero, 0)] |= (pos_left > 0);
            }
            //turn into 1 and start run
            if((pos_left > 0) & vis[pos][encode(ops, 0)] & (go_one == (go_one & 1))) {
                //cout << "hi" << endl;
                vis[pos + 1][encode(go_one, 1)] = 1; 
            }
            //state = 1
            //turn into 0
            if(vis[pos][encode(ops, 1)] & (go_zero == (go_zero & 1))) {
                vis[pos + 1][encode(go_zero, 2)] |= (real_ops > 0);
            }
            //turn into 1 and continue run
            if((pos_left > 0) & vis[pos][encode(ops, 1)]  & (go_one == (go_one & 1))) {
                vis[pos + 1][encode(go_one, 1)] = 1;
            }
            //state = 2
            //turn into 0
            if(vis[pos][encode(ops, 2)] & (go_zero == (go_zero & 1))) {
                vis[pos + 1][encode(go_zero, 2)] |= (real_ops > 0);
            }
        }
    }
    int base = max(0, abs(par_diff) - 1);
    if(base == 0) {
        return vis.back()[encode(0, 1)] | vis.back()[encode(0, 2)];
    }
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto &i : a) cin >> i;
        bool res = solve(a);
        if(res) cout << "TAK\n";
        else cout << "NIE\n";
        // cout.flush(); //!!!!!!
    }
}