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
import sys
import itertools

def eval(n, H, p):
    def calc(T1, rH):
        sc = 0
        w1 = T1.index(max(T1))
        aw1 = (p + w1) % (2 * n)
        if aw1 % 2 == 1:
            sc += 1
        m2 = -1
        w2 = -1
        for i in range(2 * n):
            if rH[i][0] > m2:
                m2 = rH[i][0]
                w2 = i 
        if w2 % 2 == 1:
            sc += 1
        return sc

    def mm(t, c_H, T1):
        if t == 2 * n:
            return calc(T1, c_H)
        cp = (p + t) % (2 * n)
        is_a = (cp % 2 == 1)
        if is_a:
            bs = -1
            for i, c in enumerate(c_H[cp]):
                nH = list(c_H)
                nH[cp] = c_H[cp][:i] + c_H[cp][i+1:]
                s = mm(t + 1, tuple(nH), T1 + (c,))
                bs = max(bs, s)
            return bs
        else:
            bs = 3
            for i, c in enumerate(c_H[cp]):
                nH = list(c_H)
                nH[cp] = c_H[cp][:i] + c_H[cp][i+1:]
                s = mm(t + 1, tuple(nH), T1 + (c,))
                bs = min(bs, s)
            return bs
    return mm(0, H, ())

def dist(n):
    C = tuple(range(1, 4 * n + 1))
    def dfs(p, C):
        if p == 2 * n:
            yield ()
            return
        for h in itertools.combinations(C, 2):
            rC = tuple(c for c in C if c not in h)
            for r in dfs(p + 1, rC):
                yield (h,) + r
    yield from dfs(0, C)

def solve(n, arr):
    cnt = 0
    for h in dist(n):
        f = True
        for i in range(2 * n):
            s = eval(n, h, i)
            if s != arr[i]:
                f = False
                break
        cnt += f
    return cnt

def val(arr):
    if 0 in arr and 2 in arr:
        return False
    for i in range(1, len(arr)):
        ps = i + 1 
        if ps % 2 == 0:
            if arr[i] > arr[i-1]:
                return False
        else:
            if arr[i] < arr[i-1]:
                return False
    return True

inp = sys.stdin.read().split()
if inp:
    t = int(inp[0])
    i = 1
    for _ in range(t):
        n = int(inp[i])
        i += 1
        arr = []
        for _ in range(2 * n):
            arr.append(int(inp[i]))
            i += 1
        if not val(arr):
            print(0)
        else:
            ans = solve(n, arr)
            print(ans)