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
#include <bits/stdc++.h>
#define st first
#define sc second
using namespace std;
typedef long long ll;
const int maxT = 100'000;
vector< bool > odp;

void solve(){
    int N;
    cin >> N;
    deque< int > tab;
    int prawo = 0, lewo = 0;
    bool ok = 1;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        tab.push_back(a);
    }
    while(tab.front()==0 && !tab.empty()){ tab.pop_front(); }
    while(tab.back()==0 && !tab.empty()){ tab.pop_back(); }
    N = tab.size();
    if(N == 0){ tab.push_back(1); N++; }
    for(int i = 0; i < N; i++){
        prawo = tab[i] - prawo;
        if(i!=N-1 && prawo < 0) ok = 0;
    }
    for(int i = N-1; i >= 0; i--){
        lewo = tab[i] - lewo;
        if(i!=0 && lewo < 0) ok = 0;
    }
    bool a;
    if(!ok){ a = 0; }
    else if( (prawo >= -1 && prawo <= 1) ||
             (lewo >= -1 && lewo <= 1)){ a=1; }
    else a = 0;
    odp.push_back(a);
    return;
}

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

    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        solve();
    }
    for(int t = 0; t < T; t++){
        if(odp[t]){ cout << "TAK\n"; }
        else{ cout << "NIE\n"; }
    }
}