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
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

typedef vector< set<int> > T;

void doit() {
  int n; scanf(" %d", &n);
  
  bool hadPositive = false;
  bool hadZeroAfterPositive = false;

  // Eate so many ends
  T ends(3);
  ends[0].insert(0);

  for (int i=0; i<n; ++i) {
    int a; scanf(" %d", &a); a *= 2;
    T newEnds(3);
    
    if (hadZeroAfterPositive && (a > 0)) {
      for (i++; i<n; ++i) scanf(" %d", &a);
      printf("NIE\n");
      return;
    }
    
    if (hadPositive && a > 0) {
      for (int j=0; j<3; ++j) ends[j].erase(0);
    }
 
    for (int j=0; j<3; ++j) {
      for (int k: ends[j]) {
        if (a - k >= 0) {
          newEnds[j].insert(a - k);
        }
      }
    }

    for (int j=0; j<2; ++j) {
      for (int k: ends[j]) {
        if (k > 0 && (a - k + 1 >= 0)) {
          newEnds[j+1].insert(a - k + 1);
        }
        if (a - k - 1 >= 0) {
          newEnds[j+1].insert(a - k - 1);
        }
      }
    }

    for (int k : ends[0]) {
      if (k > 1 && (a - k + 2 >= 0)) {
        newEnds[2].insert(a - k + 2);
      }
      if (a - k - 2 >= 0) {
        newEnds[2].insert(a - k - 2);
      }
    }

    if (hadPositive && (a == 0)) hadZeroAfterPositive = true; 
    if (a > 0) hadPositive = true;

    ends = std::move(newEnds);
    newEnds = T(3); 
  }

  if (ends[2].contains(0)) {
    printf("TAK\n");
  } else {
    printf("NIE\n");
  }
}

int main() {
  int t; scanf(" %d", &t);
  while (t--) doit();
  return 0;
}