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
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e6+5;
inline void MAIN(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int&i:a)cin>>i;
    while(!a.back())a.pop_back();
    reverse(a.begin(),a.end());
    while(!a.back())a.pop_back();
    if(count(a.begin(),a.end(),0))return cout<<"NIE\n",void();
    n=a.size();
    if(n==1)return cout<<(a[0]==1?"TAK\n":"NIE\n"),void();
    LL s=0;
    vector<vector<int>>f(n+1,vector<int>(3)),g(n+1,vector<int>(3)),h(n+1,vector<int>(3));
    f[0]={0,1,0},g[0]={0,0,0},h[0]={0,0,0};
    for(int i=0;i<n;++i){
        s=a[i]-s;
        if(s<-1)return cout<<"NIE\n",void();
        for(int j=-1;j<=1;++j){
            if(i<n-1?(s-j>0):(s-j==0))f[i+1][1-j]=f[i][1+j],h[i+1][1-j]=g[i][1+j]|h[i][1+j];
            if(i<n-1?(s-j+1>0):(s-j+1==0)&&1-j+1<3)g[i+1][1-j+1]=g[i][1+j]|f[i][1+j];
        }
    }
    cout<<((f[n][0]|f[n][1]|f[n][2]|g[n][0]|g[n][1]|g[n][2]|h[n][0]|h[n][1]|h[n][2])?"TAK\n":"NIE\n");
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t=1;cin>>t;while(t--)MAIN();
    return 0;
}