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>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    int l = 0, r = n;
    while (l < r && a[l] == 0) {
        l++;
    }
    while (l < r && a[r - 1] == 0) {
        r--;
    }
    a = std::vector(a.begin() + l, a.begin() + r);
    n = a.size();
    
    if (n == 0) {
        std::cout << "NIE\n";
        return;
    }
    
    if (std::find(a.begin(), a.end(), 0) != a.end()) {
        std::cout << "NIE\n";
        return;
    }
    
    std::vector<std::array<int, 4>> dp;
    
    dp.push_back({a[0], a[0], 0, 0});
    dp.push_back({a[0] - 1, a[0], 1, 0});
    dp.push_back({a[0], a[0] - 1, 0, 1});
    if (a[0] > 1 || n == 1) {
        dp.push_back({a[0] - 1, a[0] - 1, 1, 1});
    }
    
    for (int i = 1; i < n; i++) {
        std::vector<std::array<int, 4>> ndp;
        
        for (auto [l, r, st, ed] : dp) {
            for (int s = 0; st + s < 2; s++) {
                for (int e = 0; ed + e < 2; e++) {
                    // a[i] = r + nl + s = l + nr + e
                    int nl = a[i] - r - s;
                    int nr = a[i] - l - e;
                    int nst = st + s;
                    int ned = ed + e;
                    if (nl >= 0 && nr >= 0 && (nl + nr > 0 || i == n - 1)) {
                        ndp.push_back({nl, nr, nst, ned});
                    }
                }
            }
        }
        
        dp = std::move(ndp);
        std::sort(dp.begin(), dp.end());
        dp.erase(std::unique(dp.begin(), dp.end()), dp.end());
    }
    
    for (auto [l, r, st, ed] : dp) {
        if (l == 0 && r == 0 && st == 1 && ed == 1) {
            std::cout << "TAK\n";
            return;
        }
    }
    
    std::cout << "NIE\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}