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 rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<pair<int, int>> ints;
    rep(i, 0, n) cin >> arr[i];
    int lt = 0, rt = n - 1;
    while(!arr[lt]) lt++;
    while(!arr[rt]) rt--;
    rep(i, lt, rt) if(!arr[i]) { cout << "NIE\n"; return; }
    vector<int> tmp(rt - lt + 1);
    rep(i, lt, rt + 1) tmp[i - lt] = arr[i];
    swap(tmp, arr), n = rt - lt + 1;
    tmp.resize(n);
    rep(i, 0, n) tmp[i] = arr[i];
    int start = 0;
    rep(i, 0, n - 1) {
        int take = min(arr[i], arr[i + 1]);
        arr[i] -= take;
        arr[i + 1] -= take;
        if(!take) {
            ints.pb({start, i});
            start = i + 1;
        }
        if(arr[i] > 1) { cout << "NIE\n"; return; }
    }
    if(arr[n - 1] > 1) { cout << "NIE\n"; return; }
    ints.pb({start, n - 1});
    int gdzieJedynka = -1;
    rep(i, 0, n) if(arr[i] == 1) {
        if(gdzieJedynka != -1) { cout << "NIE\n"; return; }
        gdzieJedynka = i;
    }
    if(gdzieJedynka == -1 || ints[0].second == gdzieJedynka) {
        bool g = true;
        rep(i, 1, max(1ll, (ll)ints.size() - 1)) {
            vector<int> tmp2(ints[i].second - ints[i].first + 1);
            rep(j, ints[i].first, ints[i].second + 1) tmp2[j - ints[i].first] = tmp[j];
            rep(j, 0, (ll)tmp2.size()) {
                tmp2[j]--;
                if(tmp2[j] < 0) { g = false; break; }
                if(j < (ll)tmp2.size() - 1) tmp2[j + 1] -= tmp2[j];
            }
            if(!g) break;
        }
        if(gdzieJedynka != -1 || g) {
            cout << (g ? "TAK\n" : "NIE\n");
            return;
        }
    }
    if(gdzieJedynka == -1 || (gdzieJedynka >= ints.back().first && (gdzieJedynka - ints.back().first) % 2 == 0)) {
        bool g = true;
        rep(i, 1, max(1ll, (ll)ints.size() - 1)) {
            vector<int> tmp2(ints[i].second - ints[i].first + 1);
            rep(j, ints[i].first, ints[i].second + 1) tmp2[j - ints[i].first] = tmp[j];
            repD(j, (ll)tmp2.size() - 1, -1) {
                tmp2[j]--;
                if(tmp2[j] < 0) { g = false; break; }
                if(j > 0) tmp2[j - 1] -= tmp2[j];
            }
            if(!g) break;
        }
        cout << (g ? "TAK\n" : "NIE\n");
        return;
    }
    cout << (ints.size() == 1 ? "TAK\n" : "NIE\n");
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin >> t;
    rep(i, 0, t) solve();
}