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
def wypisz_runde(runda):
    k = len(runda)
    output = ["" for _ in range(k*2)]
    i = 0
    j = k*2 - 1
    for a, b in runda:
        output[i] = str(a + 1)
        output[j] = str(b + 1)
        i += 1
        j -= 1
    print(" ".join(output))


def solve(tab):
    n = len(tab)
    m = max(tab) + 1
    count = [0 for _ in range(m)]
    for x in tab:
        count[x] += 1
    for i in range(1, m):
        count[i] += count[i-1]
    for i in range(n):
        tab[i] = count[tab[i]] - 1

    prev = [-1 for i in range(n)]
    visit = [False for _ in range(n)]
    first_round = []
    second_round = []
    for i in range(n):
        if not visit[i] and tab[i] != i:
            if tab[tab[i]] == i:
                first_round.append((i, tab[i]))
                visit[i] = True
                visit[tab[i]] = True
            else:
                cur = i
                length = 0
                while not visit[cur]:
                    visit[cur] = True
                    prev[tab[cur]] = cur
                    cur = tab[cur]
                    length += 1
                pointer1 = prev[cur]
                pointer2 = tab[cur]
                if length == 3:
                    first_round.append((pointer1, pointer2))
                    second_round.append((cur, pointer2))
                else:
                    while True:
                        first_round.append((pointer1, pointer2))
                        second_round.append((pointer2, cur))
                        if length % 2 == 0 and pointer1 == tab[tab[pointer2]]:
                            second_round.append((pointer1, tab[pointer2]))
                            break
                        pointer1, cur, pointer2 = prev[pointer1], pointer1, tab[pointer2]
                        if length % 2 == 1 and tab[pointer2] == pointer1:
                            first_round.append((pointer1, pointer2))
                            second_round.append((pointer2, cur))
                            break
    if not first_round:
        print("0")
    else:
        if second_round:
            print("2")
        else:
            print("1")
        print(len(first_round)*2)
        wypisz_runde(first_round)
        if second_round:
            print(len(second_round)*2)
            wypisz_runde(second_round)


ile = int(input())
t = []
for _ in range(ile):
    t.append(int(input()))
solve(t)