Antifibo

În inima cetăţii Numeropolis, se ridica Turnul Infinitului, unde Marele Logofăt, doamna Algoria, păstra Pergamentul Armoniei Numerice. În fiecare toamnă, ea invita înăuntru cei mai îndrăzneţi adepţi ai Şcolii lui Euclid pentru a trece proba Ordinii Echilibrate.

Fiecare candidat primea un manuscris care conţinea un număr natural $N$. Misiunea era să aşeze într-un şir $A$ toate pietrele numerice distincte de la 1 până la $N$ (aranjare numită Ordine), astfel încât să nu fie respectată proprietatea interzisă:

Să existe vreun $1 \leq i \leq N - 2$, pentru care are loc $A[i]+A[i + 1]=A[i + 2]$

Legenda spune că, dacă cineva încălca această regulă, cele trei pietre se îmbrăcau într-o energie distructivă şi încercau să smulgă Pergamentul din siguranța Turnului.

Odată Ordinea încheiată, concurenţii se îndreptau spre Sala CMMDC-ului, unde fiecare pereche de pietre adiacente, $A[i], A[i + 1]$, era trecută prin piatra fermecată a Celui Mai Mare Divizor Comun. Rezultatele fiecărei examinări erau însumate, iar scorul final era:

$S = (A[1], A[2]) + (A[2], A[3]) + \ldots + (A[N - 1], A[N]).$

Cerință

Se dă un $T$ și $T$ teste. Pentru fiecare test, se citește un $N$ și trebuie să construim o Ordine, $A$, folosind toate numerele de la 1 la $N$, astfel încât niciun triplet aflat pe poziții consecutive să verifice $A[i] + A[i + 1] = A[i + 2]$. Pentru fiecare Ordine să se afișeze suma tuturor c.m.m.d.c.-urilor perechilor $A[i], A[i + 1]$, unde $1 \leq i \leq N - 1$.

Date de intrare

Fișierul de intrare antifibo.in conține:

• pe prima linie un număr natural $T$;
• pe următoarele $T$ linii câte un număr natural $N$.

Date de ieșire

Afișează în antifibo.out răspunsul pentru fiecare test pe câte două linii: pe prima cele $N$ numere în Ordine, iar pe a doua suma c.m.m.d.c.-urilor.

Restricții și precizări

• $1 \leq T \leq 1 \ 000$;
• $3 \leq N \leq 20 \ 000$;
• Se garantează că mereu există o Ordine posibilă.
• Valoarea sumei diferă pentru fiecare Ordine aleasă.
• Este obligatorie afișarea celor două rânduri pentru fiecare query, altfel nu veți primi punctajul parțial.
• Daca Ordinea este corectă, dar suma nu, se va acorda doar punctajul pentru Ordine și vice-versa.
• Pentru Ordine se acordă $60\%$ din punctajul total, iar pentru sumă $40\%$.

Exemplu

antifibo.in

6
3
4
5
6
7
8

antifibo.out

2 3 1
2
2 4 3 1
4
3 5 2 4 1
5
5 2 6 1 4 3
6
4 7 2 6 1 5 3
7
3 8 2 7 1 6 4 5
9

Explicație

Pentru testcase-ul 1, avem Ordinea: $2 \ 3 \ 1$, cum $2 + 3 = 5 ≠ 1$, convine. $(2, 3) + (3, 1) = 1 + 1 = 2$.
Pentru testcase-ul 3, avem Ordinea: $3 \ 5 \ 2 \ 4 \ 1$, cum $3 + 5 = 8 ≠ 2$ și așa mai departe, convine. $(3, 5) + (5, 2) + (2, 4) + (4, 1) = 1 + 1 + 2 + 1 = 5$.
Pentru testcase-ul 6, avem Ordinea: $3 \ 8 \ 2 \ 7 \ 1 \ 6 \ 4 \ 5$, cum $3 + 8 = 11 ≠ 2$ și așa mai departe, convine. $(3, 8)+(8, 2)+(2, 7)+ (7, 1) + (1, 6) + (6, 4) + (4, 5) = 1 + 2 + 1 + 1 + 1 + 2 + 1 = 9$.