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

#define ll long long

bool spr(vector<ll> &dane, ll idx, ll n){
    // cerr << "spr idx: " << idx << '\n';
    ll prev = dane[idx++];
    // cerr << "prev: " << prev << '\n';
    ll act;
    bool end = 0;
    while(idx <= n){
        act = dane[idx++];
        // cin >> act;
        // cerr << "idx: " << idx << " elem: " << act << '\n';
        // cerr << "prev: " << prev << '\n';
        if(end){
            if(act){
                // prev = ll_MAX;
                // break;
                return 0;
            }
            // continue;
        }
        
        else if(prev > act){
            if(prev - act >= 2){
                // prev = ll_MAX;
                // break;
                return 0;
            }
            end = 1;
            prev = 0;
            // continue;
        }

        else{
            prev = act - prev + 1;
            // if(beg) prev = max(prev - 1, 1);
        }
        // beg = 0;
        // cerr << "end: " << end << '\n';
        // cerr << "prev: " << prev << '\n';
        // cerr << "=======\n\n";
        // act_idx++;
    }
    if(prev > 1) return 0;
    else return 1;
}

bool solve(ll n){
    // cerr << "n: " << n << '\n';

    vector<ll> dane(n + 1);
    for(ll i = 1; i <= n; i++){
        cin >> dane[i]; 
    }

    ll last_plus = -1;
    for(ll i = 1; i <= n; i++){
        if(dane[i]){
            if(i >= 2 && last_plus != -1 && last_plus + 1 != i) return 0; 
            last_plus = i;
        }
    }

    ll prev = 0;
    // cin >> prev;
    ll act_idx = 1, act = 0;
    while(act_idx <= n && dane[act_idx] < 1) act_idx++;
    // while(act_idx <= n && dane[act_idx] == 1) act_idx++;
    if(act_idx > n) return 1;
    if(act_idx > 1 && dane[act_idx - 1]) act_idx--;
    // prev = dane[act_idx++];
    if(spr(dane, act_idx, n)) return 1;
    // cerr << "ok1\n";
    act_idx++;
    // cerr << "act_idx: " << act_idx << '\n';
    // cerr << "dane[act]: " << dane[act_idx] << '\n';
    if(act_idx <= n && dane[act_idx] > 1 && dane[act_idx] > dane[act_idx - 1]){
        dane[act_idx] -= dane[act_idx - 1];
        // dane[act_idx] = max(dane[act_idx], 1);
        if(spr(dane, act_idx, n)) return 1;
    }
    // cerr << "ok2\n";
    // bool end = 0, beg = 1;


    // cerr << "act_idx: " << act_idx << '\n';

    // while(act_idx <= n){
    //     cin >> act;
    //     // cerr << "idx: " << act_idx << " elem: " << act << '\n';
    //     act_idx++;
    // }

    // if(prev > 1) return 0;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll t;
    cin >> t;

    ll n;
    for(ll i = 0 ; i < t; i++){
        cin >> n;
        // cerr << "n: " << n << '\n';
        // cerr << "i: " << i << '\n';
        if(solve(n)) cout << "TAK\n";
        else cout << "NIE\n";
        // cerr << "\n\n";
    }
}