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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;

long long tab[1000009], diff1[1000009], diff2[1000009];
vector<int> v;

void solve(int t)
{
	int n, a = 0, b, s1 = 0, s2 = 0, c = -1, d = -1;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>tab[i];
		if(tab[i] != 0 && a == 0) a = 1;
		if(tab[i] == 0 && a == 1) a = 2;
		if(tab[i] != 0 && a == 2) a = 3;
	}
	if(a == 3) {
		cout<<"NIE\n";
		return;
	}
	for(int i=1; i<=n; i++) {
		if(tab[i] != 0) {
			a = i;
			break;
		}
	}
	if(a > 1) {
		b = 1;
		while(tab[a] != 0) {
			tab[b] = tab[a];
			a++;
			b++;
		}
		n = b - 1;
	}
	else {
		for(int i=1; i<=n; i++) {
			if(tab[i] == 0) {
				n = i - 1;
				break;
			}
		}
	}
	
	for(int i=1; i<=n; i++) {
		if(i % 2 == 1) s1 += tab[i];
		else s2 += tab[i];
	}
	
	tab[0] = tab[n+1] = 0;
	
	if(s1 > s2) a = b = 1;
	else if(s2 > s1) a = b = 0;
	else {
		a = 1;
		b = 0;
	}
	for(int i=1; i<=n; i++) {
		if(tab[i] == tab[i-1] + tab[i+1]) {
			if(i % 2 == a && c == -1) c = i;
			else if(i % 2 == b && d == -1) d = i;
			else {
				cout<<"NIE\n";
				return;
			}
		}
	}
	
	if(c != -1 && d != -1) {
		for(int i=min(c,d)+1; i<max(c,d); i++) tab[i]++;
		diff1[1] = tab[1];
		for(int i=2; i<n; i++) diff1[i] = tab[i] - diff1[i-1];
		diff2[n-1] = tab[n];
		for(int i=n-2; i>=1; i--) diff2[i] = tab[i+1] - diff2[i+1];
		for(int i=1; i<n; i++) {
			if(diff1[i] <= 0 || diff2[i] <= 0) {
				cout<<"NIE\n";
				return;
			}
		}
		for(int i=1; i<n; i++) {
			if(diff1[i] != diff2[i]) {
				cout<<"NIE\n";
				return;
			}
		}
		cout<<"TAK\n";
		return;
	}
	
	diff1[1] = tab[1];
	for(int i=2; i<n; i++) diff1[i] = tab[i] - diff1[i-1];
	diff2[n-1] = tab[n];
	for(int i=n-2; i>=1; i--) diff2[i] = tab[i+1] - diff2[i+1];
	for(int i=1; i<n; i++) {
		if(diff1[i] < 0 || diff2[i] < 0) {
			cout<<"NIE\n";
			return;
		}
	}
	
	if(s1 == s2) {
		for(int i=1; i<n; i++) {
			if(diff1[i] != diff2[i]) {
				cout<<"NIE\n";
				return;
			}
		}
		cout<<"TAK\n";
	}
	else if(s1 == s2 + 1 || s2 == s1 + 1) {
		for(int i=1; i<n; i++) {
			if(i % 2 == 1) {
				if((s1 > s2 && diff1[i] != diff2[i] + 1) || (s1 < s2 && diff1[i] + 1 != diff2[i])) {
					cout<<"NIE\n";
					return;
				}
			}
			else {
				if((s1 > s2 && diff1[i] + 1 != diff2[i]) || (s1 < s2 && diff1[i] != diff2[i] + 1)) {
					cout<<"NIE\n";
					return;
				}
			}
		}
		cout<<"TAK\n";
	}
	else cout<<"NIE\n";
	return;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
	int t;
	cin>>t;
	//while(t--) solve();
	for(int i=1; i<=t; i++) solve(i);
	return 0;
}