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

constexpr auto CONSUME_ZERO_SS = 0;
constexpr auto CONSUME_ONE_SS = 1;
constexpr auto CONSUME_TWO_SS = 2;
using Buffer = std::set<int>;

void add(Buffer& dst, const Buffer& src, const int& dstValue, const int& minimalValue) {
  for (const auto& v : src) {
    if (minimalValue <= dstValue - v) {
      dst.insert(dstValue - v);
    }
  }
}

void process(Buffer* buffers, Buffer* tmpBuffers, const int value) {
  add(tmpBuffers[CONSUME_TWO_SS], buffers[CONSUME_TWO_SS], 2 * value, 0);
  add(tmpBuffers[CONSUME_TWO_SS], buffers[CONSUME_ONE_SS], 2 * value - 1, 0);
  add(tmpBuffers[CONSUME_TWO_SS], buffers[CONSUME_ZERO_SS], 2 * value - 2, 0);
  add(tmpBuffers[CONSUME_ONE_SS], buffers[CONSUME_ONE_SS], 2 * value, 1);
  add(tmpBuffers[CONSUME_ONE_SS], buffers[CONSUME_ZERO_SS], 2 * value - 1, 1);
  add(tmpBuffers[CONSUME_ZERO_SS], buffers[CONSUME_ZERO_SS], 2 * value, 2);

  std::swap(tmpBuffers[CONSUME_ZERO_SS], buffers[CONSUME_ZERO_SS]);
  std::swap(tmpBuffers[CONSUME_ONE_SS], buffers[CONSUME_ONE_SS]);
  std::swap(tmpBuffers[CONSUME_TWO_SS], buffers[CONSUME_TWO_SS]);
}

bool isOk(const std::vector<int>& values) {
  Buffer buffers[3];
  Buffer tmpBuffers[3];
  int nonZeroBlocks = 0;
  int lastValue = 0;
  bool initialized = false;

  for (const auto& value : values) {
    if (value != 0) {
      if (lastValue == 0) {
        nonZeroBlocks++;
      }
      if (1 < nonZeroBlocks) {
        return false;
      }
      if (initialized) {
        buffers[CONSUME_TWO_SS].erase(0);
        process(buffers, tmpBuffers, value);
        tmpBuffers[CONSUME_TWO_SS].clear();
        tmpBuffers[CONSUME_ONE_SS].clear();
        tmpBuffers[CONSUME_ZERO_SS].clear();
      } else {
        initialized = true;
        buffers[CONSUME_TWO_SS].insert(value * 2 - 2);
        buffers[CONSUME_ONE_SS].insert(value * 2 - 1);
        buffers[CONSUME_ZERO_SS].insert(value * 2);
      }
    }
    lastValue = value;
  }
  return 0 < buffers[CONSUME_TWO_SS].count(0);
}

int main() {
  int t, n, value;
  scanf("%d", &t);
  for (int i = 0; i < t; ++i) {
    scanf("%d", &n);
    std::vector<int> values;
    for (int j = 0; j < n; ++j) {
      scanf("%d", &value);
      values.push_back(value);
    }
    isOk(values) ? printf("TAK\n") : printf("NIE\n");
  }
  return 0;
}