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
// {{{ file: wyl.cpp | time: 17:18 11.03.2025
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define each(...)    for (auto& __VA_ARGS__)
#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define rev(i, b, e) for (int i = (e); i >= (b); i--)
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define tC template<class
#define $(x) #x<<'='<<(x)<<' '

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vpi = vector<pii>;
using vpl = vector<pll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
tC T, class C=greater<T>> using min_priority_queue = priority_queue<T,vector<T>,C>;
tC T> int sz(const T& a) { return (int)a.size(); }
tC T> bool amin(T& a, T b) { return b < a ? a = b, 1 : 0; }
tC T> bool amax(T& a, T b) { return b > a ? a = b, 1 : 0; }
const int oo = 1e9+1;
const ll OO = ll(1e18)+1;

auto now() { return chrono::high_resolution_clock::now().time_since_epoch().count(); }
mt19937 rnd(4488);
tC T> T rand(T lo, T hi) { return uniform_int_distribution<T>{lo,hi}(rnd); }

struct Debug {
#ifdef SPONGE
  tC T>Debug operator<<(const T& x) { cerr<<"\033[1;33m"<<x<<"\033[0m"; return *this; }
#else
  tC T>Debug operator<<(const T&) { return *this; }
#endif
} dbg;

namespace { void solve(); }
// }}}

int main()
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(15);
  cout.setf(ios::fixed,ios::floatfield);
  cerr.precision(15);
  cerr.setf(ios::fixed,ios::floatfield);
  //rnd.seed(now());
  int t=1;
  cin>>t;
  rep(i,1,t){
    //cout<<"Case #"<<i<<": ";
    solve();
  }
}

namespace {

const int N=1e6+1;
int n;
ll a[N],dp[N][2][2];

void solve()
{
  cin>>n;
  rep(i,1,n) cin>>a[i];

  int poc=0,kon=0;
  rep(i,1,n) if(a[i]>0){
    if(poc==0) poc=i;
    kon=i;
  }

  ll suma_even=0,suma_odd=0;
  rep(i,poc,kon){
    if(i%2==0) suma_even+=a[i];
    else suma_odd+=a[i];
  }

  if(abs(suma_even-suma_odd)>1){
    cout<<"NIE"<<endl;
    return;
  }

  int s,t;
  if(suma_even==suma_odd){ s=0; t=1; }
  else if(suma_even>suma_odd){ s=0; t=0; }
  else{ s=1; t=1; }

  rep(i,poc,kon) a[i]=2*a[i];
  rep(i,poc,kon) rep(x,0,1) rep(y,0,1) dp[i][x][y]=-1;

  rep(i,poc,kon){
    if(i==poc){
      dp[poc][0][0]=a[i];
    }
    else{
      rep(x,0,1) rep(y,0,1){
        if(dp[i-1][x][y]>0 && dp[i-1][x][y]<=a[i]){
          dp[i][x][y]=a[i]-dp[i-1][x][y];
        }
      }
    }
    if(s==i%2) rep(y,0,1) amax(dp[i][1][y],dp[i][0][y]-1);
    if(t==i%2) rep(x,0,1) amax(dp[i][x][1],dp[i][x][0]-1);
  }

  if(dp[kon][1][1]==0) cout<<"TAK"<<endl;
  else cout<<"NIE"<<endl;
}

}