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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

bool go(const vector<int>& a, int n) {
    vector<pair<int, int>> c, e;
    c.push_back(make_pair(0, a[0]));
    for (int i = 1; i <= n; i++) {
        e.clear();
        for (auto [k, x] : c) {
            if (k == -1 && a[i] == 0) e.push_back(make_pair(-1, -1));
            else if (k != -1) {
                for (int pr = 0; pr+k <= 2 && pr+k <= x; pr++) {
                    for (int le = 0; le+pr+k <= 2; le++) {
                        if (k+pr+le == 0) {
                            if (!x) {
                                e.push_back(make_pair(0, a[i]));
                            } else {
                                if (x == 1 && a[i] == 0) e.push_back(make_pair(-1, -1));
                                if (a[i] > x) e.push_back(make_pair(0, a[i]-x));
                            }
                        } else {
                            if (x >= le+pr+k && a[i]-le >= x && a[i]-le >= k+le+pr) {
                                e.push_back(make_pair(k+pr+le, a[i]-(x-k-pr)));
                            }
                            if (k+pr+le == 2 && a[i]-le == x-1) {
                                e.push_back(make_pair(-1, -1));
                            }
                        }
                    }
                }
            }
        }
        c = e;
        sort(c.begin(), c.end());
        c.erase(unique(c.begin(), c.end()), c.end());
        //printf(" :: %d\n", i); for (auto [k, x] : c) printf("%d %d\n", k, x);
    }
    for (auto [k, x] : c) {
        if (k == -1) return true;
    }
    return false;
}

int main() {
  int tt; 
	scanf("%d", &tt);
	while (tt--) {
		int n;
		scanf("%d", &n);
        vector<int> a(n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
        a.push_back(0);
        puts(go(a, n) ? "TAK" : "NIE");
	}
	return 0;
}