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
#include <bits/stdc++.h>
using namespace std;

typedef int64_t ll;
typedef uint64_t ull;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
constexpr ll LINF = 1e18;
constexpr int INF = 1e9;

bool is_solved(vi &a, int n) {
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            return false;
        }
    }

    return true;
}

bool solve(vi &a, int n, bool reduce_by_one = false) {
    int pos = 0;
    while (a[pos] == 0) { ++pos; }
    int start = pos;
    --a[pos];

    if (reduce_by_one) {
        int new_pos = pos + 1;
        while (new_pos < n && a[new_pos] != 0) {
            --a[new_pos];
            ++new_pos;
        }
        start = new_pos - 1;
    }

    while (true) {
        int reduction = min(a[pos], a[pos + 1] - 1);
        if (reduction == -1) {
            break;
        }

        a[pos] -= reduction;
        a[pos + 1] -= reduction + 1;
        pos += 1;
    }

    // step back
    if (pos > 0 && a[pos - 1] >= 1) {
        --a[pos - 1];
    }

    // step from start
    if (start + 1 < n && a[start + 1] == 1) {
        --a[start + 1];
    } else if (start > 0 && a[start - 1] == 1) {
        --a[start - 1];
    }

    return is_solved(a, n);
}

bool solve_cases(vi &a, vi &b, int n) {
    if (solve(b, n, false)) {
        return true;
    }

    // Reduced by one
    for (int i = 0; i < n; ++i) {
        b[i] = a[i];
    }
    b[n] = 0;

    if (solve(b, n, true)) {
        return true;
    }

    // Reversed
    for (int i = 0; i < n; ++i) {
        b[i] = a[n - i - 1];
    }
    b[n] = 0;

    if (solve(b, n)) {
        return true;
    }

    // Reversed, reduced by 1
    for (int i = 0; i < n; ++i) {
        b[i] = a[n - i - 1];
    }
    b[n] = 0;

    if (solve(b, n, true)) {
        return true;
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t, n;
    cin >> t;

    vi a(1000002);
    vi b(1000002);
    while (t--) {
        cin >> n;

        a[n] = 0;
        b[n] = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            b[i] = a[i];
        }

        cout << (solve_cases(a, b, n) ? "TAK" : "NIE") << '\n';
    }

    return 0;
}