År 2077 blir det enkelt att konstruera tävlingsuppgifter. Robotar genererar ett problem genom att välja några slumpmässiga operationer och löser det sedan. En uppgiftskonstruktör behöver bara kontrollera om problemet är korrekt eller inte.

Här är ett problem från 2077:

Givet en permutation $p_1, p_2, \dots, p_n$, där det garanteras att $n$ är jämnt. Du vill sortera permutationen med hjälp av endast en typ av operation:

• FakeSort(l,r): Du måste garantera att $r - l + 1$ är jämnt. Låt $k = r - l + 1$, då kommer de $k/2$ största elementen och de $k/2$ minsta elementen i den sammanhängande delsekvensen $p_l, p_{l+1}, \dots, p_r$ att sorteras oberoende av varandra. Det vill säga, låt $L_1, L_2, \dots, L_{k/2}$ vara indexen för de $k/2$ största talen, och $S_1, S_2, \dots, S_{k/2}$ vara indexen för de $k/2$ minsta talen. Vi sorterar först talen på indexen $L_1 \sim L_{k/2}$, och sorterar sedan talen på indexen $S_1 \sim S_{k/2}$.

Här är ett konkret exempel; anta att permutationen är $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Om vi anropar FakeSort(2,7):

• $k = r - l + 1 = 6$. Den sammanhängande delsekvensen $p_l, p_{l+1}, \dots, p_r$ är $\{5, 7, 1, 8, 6, 4\}$; vi kommer att sortera de $3$ största talen och de $3$ minsta talen i denna sekvens oberoende av varandra.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; de $3$ största talen är markerade med fetstil. Efter sortering blir de $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; de $3$ minsta talen är markerade med fetstil. Efter sortering blir de $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Så $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ blir efter FakeSort(2,7) lika med $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Använd högst $114$ operationer för att sortera permutationen eller avgör att det är omöjligt. Det går att bevisa att om en permutation kan sorteras med denna operation, så finns det ett sätt som använder högst $114$ operationer.

Indata

Indatan innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^3$), antalet testfall.

För varje testfall innehåller den första raden ett jämnt heltal $n$ ($4 \le n \le 10^5$), permutationens längd.

Den andra raden innehåller $n$ heltal $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), permutationen som du ska sortera. Det garanteras att $p$ är en permutation.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, om det är omöjligt att sortera permutationen, skriv ut $-1$.

Annars, skriv ut ett heltal $k$ ($0 \le k \le 114$), som anger antalet använda operationer.

På de följande $k$ raderna, skriv ut $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ är jämnt) på varje rad, vilket anger att FakeSort(l,r) utförs.

Exempel

Exempelindata 1

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

Exempelutdata 1

1
1 4
-1
2
4 7
1 6