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
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif

const int maxN = 1 << 20;

int n, T[maxN];
long long pref[maxN], suf[maxN];
bool zeroPref[2][maxN], zeroSuf[2][maxN];

void load()
{
	scanf ("%d", &n);

	FOR(i, 1, n+1)
	{
		scanf ("%d", T+i);
		if (i == 1 and T[i] == 0)
			--i, --n;
	}
	while (T[n] == 0)
		--n;
}

void f(long long P[maxN], bool zeroOcc[2][maxN])
{
	FOR(i, 1, n+1)
	{
		P[i] = 1ll * T[i] - P[i-1];
		zeroOcc[0][i] = zeroOcc[0][i-1];
		zeroOcc[1][i] = zeroOcc[1][i-1];

		if (P[i-1] < 0ll)
			P[i] = -1ll;
		if (P[i] == 0)
			zeroOcc[i&1][i] = true;
	}
}

void precalc()
{
	f(pref, zeroPref);

	std::reverse(T + 1, T + n+1);
	f(suf, zeroSuf);
	std::reverse(T + 1, T + n+1);

	std::reverse(suf + 1, suf + n+1);
	std::reverse(zeroSuf[0] + 1, zeroSuf[0] + n+1);
	std::reverse(zeroSuf[1] + 1, zeroSuf[1] + n+1);
}

void solve()
{
	load();
	precalc();

	bool res = pref[n] == 1ll and not zeroPref[0][n] and not zeroPref[1][n];

	FOR(i, 1, n)
	{
		if (res or pref[i] < 0)
			break;

		bool prefNoZeros = not zeroPref[0][i] and not zeroPref[1][i];
		bool sufValid = not zeroSuf[0][i+1] and not zeroSuf[1][i+1] and suf[i+1] > 0;

		if (not sufValid)
			continue;

		if (prefNoZeros and 1ll*T[i] - 1 == pref[i-1] + suf[i+1])
			res = true;

		int par = i&1;

		if (pref[i] == suf[i+1] and not zeroPref[par][i])
			res = true;
		if (pref[i] == suf[i+1] - 1 and not zeroPref[par ^ 1][i])
			res = true;
	}

	printf("%s\n", res ? "TAK" : "NIE");
}

int main()
{
	int tc = 1;
	scanf ("%d", &tc);	
	FOR(cid, 1, tc+1)
		solve();
	return 0;
}