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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
vector<ll> f[1000003][3];
ll c[1000003];
void solve()
{
	int n=read();
	int shift=1;
	for(int i=1; i<=n; ++i) c[i]=read();
	while(!c[shift]) ++shift;
	for(int i=shift; i<=n; ++i) c[i-shift+1]=c[i];
	n-=shift-1;
	while(!c[n]) --n;
	for(int i=1; i<=n; ++i)
		for(int j=0; j<3; ++j)
			f[i][j].clear();
	f[1][2].push_back(c[1]+1),
	f[1][1].push_back(c[1]),
	f[1][0].push_back(c[1]-1);
	auto work=[&](vector<ll> &o){
		sort(o.begin(),o.end());
		o.erase(unique(o.begin(),o.end()),o.end());
		return ;
	};
	for(int i=2; i<=n+1; ++i)
		for(int j=0; j<3; ++j)
		{
			work(f[i-1][j]);
			for(ll x:f[i-1][j])
				for(int a=0; a<=j; ++a)
					for(int b=0; a+b<=j; ++b)
						if(c[i]-x+j-b-a>=0&&
						((c[i]-a-b-1>=x-a-1&&x-a-1>=0)
						||(c[i]-a-b-1==-1&&x-a-1==-1)))
							f[i][j-b-a].push_back(c[i]-x+j-b-a);
		}
	bool ok=0;
	for(auto i:f[n][0]) ok|=(i==0);
	if(ok) puts("TAK");
	else puts("NIE");
}
signed main()
{
	for(int T=read(); T--; solve());
	return 0;
}