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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,m,s,a,b,t;

vector<ll>unq(vector<ll>v){
    vector<ll>ans;
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    while(v.size() && v.back()<0)v.pop_back();
    reverse(v.begin(),v.end());
    if(v.empty())return {};
    ans.pb(v[0]);
    for(ll i=1;i<v.size();i++){
        if(v[i]!=v[i-1])
            ans.pb(v[i]);
    }
    return ans;
}
vector<ll>dp[1000007][3];//zakladajac ze jak od prawej to juz jestem
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    vector<ll>v;
    while(t--){
        cin>>n;
        ll N=n;
        v.clear();
        for(ll i=0;i<N;i++){
            cin>>a;
            n--;
            if(a==0 && v.empty())continue;
            n++;
            v.pb(a);
        }
        while(v.size() && v.back()==0){
            v.pop_back();
            n--;}
        dp[0][0]={v[0]-1};
        dp[0][1]={v[0]-1};
        dp[0][2]={v[0]-1};
        for(ll i=1;i<n;i++){
            dp[i][0].clear();
            dp[i][1].clear();
            dp[i][2].clear();
            for(ll j : dp[i-1][2]){
                if(j>=1)
                    dp[i][2].pb(v[i]-j);
            }
            for(ll j : dp[i-1][1]){
                dp[i][2].pb(v[i]-1-j);
            }
            for(ll j : dp[i-1][0]){
                dp[i][2].pb(v[i]-2-j);
            }
            dp[i][2]=unq(dp[i][2]);
            for( ll j : dp[i-1][0]){
                dp[i][0].pb(v[i]-2-j);
            }
            dp[i][0]=unq(dp[i][0]);
            for( ll j : dp[i-1][0]){
                dp[i][1].pb(v[i]-2-j);
            }
            for( ll j : dp[i-1][1]){
                dp[i][1].pb(v[i]-1-j);
            }
            dp[i][1]=unq(dp[i][1]);
        }
        if(dp[n-1][2].size() && dp[n-1][2][0]==0)
            cout<<"TAK\n";
        else
            cout<<"NIE\n";
    }
    return 0;
}