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
127
128
129
130
131
132
133
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

const long long INF = 1e12 + 7;
//fstream dane, wyniki;

void solve(){
    int n;

    bool answer = true;

    cin>>n;

    long long sum = 0;

    int first = -1;
    int last = -1;
    bool end = false;

    vector<long long> v;

    long long x, minimum = INF;

    pair<long long,long long> two_first;

    for(int i=0;i<n;i++){
        cin>>x;
        sum += x;
        if(first == -1 && x != 0){
            first = i;
        }
        if(first != -1 && x == 0){
            end = true;
        }
        if(first != -1 && end && x != 0){
            answer = false;
        }   
        if(first != -1 && !end){
            last = i;
            v.push_back(x);
            if(v.size() == 4){
                v[0] = v[1];
                v[1] = v[2];
                v[2] = v[3];
                v.pop_back();
            }
            if(v.size() == 3){
                minimum = min(v[0] + v[2] - v[1], minimum);
            }
            if(v.size() == 2){
                two_first = {v[0], v[1]};
            }
        }
    }
    //cout<<"SIZE: "<<last - first + 1<<" "<<sum<<" "<<minimum<<"\n";
    if(!answer){
        cout<<"NIE\n";
    }
    else{
        int size = last - first + 1;
        if(size >= 3){
            if(two_first.first <= two_first.second && v[1] >= v[2]){
                if(size >= 5){
                    if(minimum >= 0){
                        cout<<"TAK\n";
                    }
                    else{
                        cout<<"NIE\n";
                    }
                }
                else if(size == 4){
                    if(sum%2 == 0 && minimum >= 1){
                        cout<<"TAK\n";
                    }
                    else if(sum%2 == 1 && minimum >= 0){
                        cout<<"TAK\n";
                    }
                    else{
                        cout<<"NIE\n";
                    }
                }
                else{
                    if(sum%2 == 0 && minimum == 0){
                        cout<<"TAK\n";
                    }
                    else if(sum%2 == 1 && (minimum == -1) || (minimum == 1)){
                        cout<<"TAK\n";
                    }
                    else{
                        cout<<"NIE\n";
                    }
                }
            }
            else{
                cout<<"NIE\n";
            }
        }
        else if(size == 2){
            if(abs(v[0] - v[1]) <= 1){
                cout<<"TAK\n";
            }
            else{
                cout<<"NIE\n";
            }
        }
        else if(size == 1){
            if(sum == 1){
                cout<<"TAK\n";
            }
            else{
                cout<<"NIE\n";
            }
        }
    }

}

int main(){
    //dane.open("test.txt");
    //wyniki.open("wyniki.txt");
    int t;
    cin>>t;

    while(t--){
        solve();
    }
    //dane.close();
   // wyniki.close();
    return 0;
}