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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator<<(auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
auto operator<<(auto &o, auto a) -> decltype(all(a), o);
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", [](auto... arg_) { (( cerr << arg_ << ", " ), ...) << '\n'; }(x)
#else
#define deb(...) 0
#endif

bool alternating(vector<ll> v) {
    rep(i, sz(v) - 1) {
        if (v[i] > v[i+1]) return false;
        v[i+1] -= v[i];
    }
    return v.back() == 0;
}

bool solve(vector<ll> v) {
    int n = sz(v);

    while (v.back() == 0) v.pop_back();
    reverse(all(v));
    while (v.back() == 0) v.pop_back();
    n = sz(v);

    if (count(all(v), 0))
        return false;

    rep(bg, 2) rep(en, 2) {
        auto vhere = v;
        fwd(i, bg, n - en)
            vhere[i]--;
        if (alternating(vhere))
            return true;
    }
    return false;
}

namespace checker {
template<int n, int lim>
void iter() {
    map<array<int, n>, bool> mp;
    deb(n, lim);

    array<int, n> v{};
    auto rec_iter = [&](auto f, int id) -> void {
        if (id == n) {
            mp[v] = false;
            return;
        }
        for (v[id] = 0; v[id] < lim; ++v[id])
            f(f, id + 1);
    };
    rec_iter(rec_iter, 0);
    deb(n, lim, sz(mp));

    v = array<int, n>{};

    auto rec_go = [&](auto f, int id) -> void {
        if (id < 0 || id >= n || v[id]+1 >= lim) return;

        ++v[id];
        mp[v] = true;
        f(f, id - 1);
        f(f, id + 1);
        --v[id];
    };

    rep(st, n) {
        rec_go(rec_go, st);
    }

    assert(!accumulate(all(mp.begin()->st), 0));
    mp.erase(mp.begin()); // all zeroes
    for (auto [tc, exp] : mp) {
        bool has = solve(vector<ll>(all(tc)));
        if (has != exp) {
            deb(tc);
            deb(has, exp);
            assert(false);
        }
    }
}
};

void solve() {
    int n;
    cin >> n;
    vector<ll> v(n);
    rep(i, n) cin >> v[i];
    cout << (solve(v) ? "TAK\n" : "NIE\n");
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    int z = 1;
    cin >> z;
    rep(_, z) solve();

    // checker::iter<1, 15>();
    // checker::iter<2, 12>();
    // checker::iter<3, 11>();
    // checker::iter<4, 8>();
    // checker::iter<5, 7>();
    // checker::iter<6, 5>();
    // checker::iter<7, 4>();

    cout << flush;
    _Exit(0);
}