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
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> vec;
int pos = 1;
int zeros = 0;
int n;

bool bt(){
	if(zeros == n) return 1;
	if(vec[pos] == 0 && vec[pos-1] > 0 && vec[pos+1] > 0) return 0;
	bool l = 0, r = 0;
	//ruch w lewo
	if(pos > 1 && vec[pos-1]){
		pos--;
		vec[pos]--;
		if(vec[pos] == 0) zeros++;
		//
		l = bt();
		//
		if(vec[pos] == 0) zeros--;
		vec[pos]++;
		pos++;
	}	
	
	if(l) return 1;
	
	//ruch w prawo
	if(pos < n && vec[pos+1]){
		pos++;
		vec[pos]--;
		if(vec[pos] == 0) zeros++;
		//
		r = bt();
		//
		if(vec[pos] == 0) zeros--;
		vec[pos]++;
		pos--;
	}	
	return r;
}

void solve(){
	cin >> n;
	vector<int> v(n+7, 0);
	
	for(int i=1; i<=n; i++) cin >> v[i];	
	
	//usuwanie zer z poczatku i konca
	{
		vector<int> v_bez_zer(n+7,0);
	
		int pocz = 1;
		int tmp = 1;
		while(v[tmp] == 0) tmp++;
		pocz = tmp;
		tmp = n;
		while(v[tmp] == 0) tmp--;
		n = tmp;
		
		int idx = 1;
		for(int i=pocz; i<=n; i++) v_bez_zer[idx++] = v[i];
		swap(v, v_bez_zer);
		n = n-pocz+1;
	}
	
	//sprawdzanie czy w ciagu nie ma przerwy
	for(int i=1; i<=n; i++){
		if(v[i] == 0){
			cout << "NIE\n";
			return;
		}
	}
	
	vec = v;
	bool ans = 0;
	pos = 1;
	
	while(ans == 0 && pos <= n){
		vec[pos]--;
		zeros = (vec[pos] == 0);
		ans |= bt();
		vec[pos]++;
		pos++;
	}
	
	if(ans) cout << "TAK\n";
	else cout << "NIE\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int T;
	cin >> T;
	
	while(T--){
		solve();
	}
	
	return 0;
}