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
from functools import lru_cache

def can_form_sequence(counts):
    """
    Given a list 'counts' where counts[i] is the number of times the number i+1 must appear,
    determine if there is a walk (starting anywhere) moving only ±1 that produces these counts.
    """
    n = len(counts)
    total = sum(counts)
    if total == 0:
        return True  # trivial, no visits

    # The state of our search is: (current_position, remaining_counts_tuple)
    # current_position is an index in 0..n-1 (representing number = index+1).
    # remaining_counts is a tuple of length n telling how many times each number still needs to be used.
    @lru_cache(maxsize=None)
    def dfs(cur, remaining_counts):
        # remaining_counts is a tuple; if its sum is 0, we have used up all counts.
        if sum(remaining_counts) == 0:
            return True

        # try moving left and right (neighbors differ by 1)
        for nxt in (cur - 1, cur + 1):
            if 0 <= nxt < n and remaining_counts[nxt] > 0:
                # build the new state by "using" one occurrence at nxt
                new_counts = list(remaining_counts)
                new_counts[nxt] -= 1
                new_state = tuple(new_counts)
                if dfs(nxt, new_state):
                    return True
        return False

    # try every possible starting position that has a positive count
    for start in range(n):
        if counts[start] > 0:
            new_counts = list(counts)
            new_counts[start] -= 1
            if dfs(start, tuple(new_counts)):
                return True
    return False


# --- Example usage:
if __name__ == '__main__':
    # examples = [
    #     ([1, 3, 1], True),   
    #     ([5, 7], False),
    #     ([0, 1, 0], True),
    #     ([2], False),
    #     ([3, 3, 2, 1, 0, 0], True),
    #     ([1, 3, 2, 2, 3], False),
    #     ([1, 0, 1], False)
    # ]
    
    # for counts, expected in examples:
    #     res = can_form_sequence(counts)
    #     print(f"Counts: {counts} => Possible? {res} (expected: {expected})")

    # Read input from stdin
    num_examples = int(input())
    
    for _ in range(num_examples):
        length = int(input())
        counts = list(map(int, input().split()))
        
        result = can_form_sequence(counts)
        print("TAK" if result else "NIE")