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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>

int t, n;
int A[1000006];
int B[1000006];
bool valid_input = true;

void solve();
void read_input();
void print_result();
void reset_globals();
void is_possible();
bool valid_left(int, int, int);
bool valid_right(int, int, int);
void debug() {
    std::cout << n << "\n";
    for (int i = 0; i < n; ++i) {
        std::cout << A[i] << " ";
    }
    std::cout << "\n";
    for (int i = 0; i < n; ++i) {
        std::cout << B[i] << " ";
    }
    std::cout << "\n\n";
}

int main() {
    std::cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

void solve() {
    read_input();
    is_possible();
    print_result();
    reset_globals();
}

void is_possible() {
//    debug();
    int lo = 0, hi = n - 1;
    while (A[lo] == 0) {
        ++lo;
    }
    while (A[hi] == 0) {
        --hi;
    }
    int num = hi - lo + 1;

    if (num == 1) {
        if (A[lo] != 1) {
            valid_input = false;
            return;
        }
    }
    if (num == 2) {
        if (std::abs(A[lo] - A[hi]) > 1) {
            valid_input = false;
            return;
        }
    }
    for (int i = lo; i <= hi; ++i) {
        if (A[i] == 0) {
            valid_input = false;
            return;
        }
    }

    for (int i = lo; i < hi; ++i) {
        int max_connections = std::max(std::min(A[i] - 1, A[i + 1] - 1), 0);
        A[i + 1] -= max_connections;
        A[i] -= max_connections;
    }
    for (int i = hi; i > lo; --i) {
        int max_connections = std::max(std::min(B[i] - 1, B[i - 1] - 1), 0);
        B[i - 1] -= max_connections;
        B[i] -= max_connections;
    }
//    debug();
    
    valid_input = valid_left(lo, hi, num) | valid_right(lo, hi, num);
}

bool valid_left(int lo, int hi, int num) {
    int unnormal = 0;
    int two_idx = -1;
    int cnt_3s = 0;
    for (int i = lo; i <= hi; ++i) {
        if (A[i] > 3) {
            return false;
        }
        if (A[i] > 1) {
            ++unnormal;
        }
        if (A[i] == 3) {
            ++cnt_3s;
        }
        if (A[i] == 2) {
            two_idx = i;
        }
    }
    if (unnormal > 1) {
        return false;
    }

    if (cnt_3s == 1) {
        if (num > 3) {
            return false;
        }
        if (A[lo] == 1 && A[lo + 1] == 3 && A[hi] == 1) {
            return true;
        }
        else {
            return false;
        }
    }
//    debug();

    if (two_idx != -1 && two_idx != lo && two_idx != hi) {
        if (A[two_idx - 1] == 0 || A[two_idx + 1] == 0) {
            return false;
        }
    }
    return true;
}

bool valid_right(int lo, int hi, int num) {
    return false;
}

void read_input() {
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> A[i];
        B[i] = A[i];
    }
}

void reset_globals() {
    std::fill(A, A + n, 0);
    std::fill(B, B + n, 0);
    valid_input = true;
    n = 0;
}

void print_result() {
    if (valid_input) {
        std::cout << "TAK\n";
    } else {
        std::cout << "NIE\n";
    }
}