Annettuna on lista, jossa on luvut $1,2,\dots,n$ jossain järjestyksessä. Listan alkiot on indeksoitu kokonaisluvuin $1$:stä alkaen.

Joka siirrolla saat valita kaksi listan alkiota, jotka eivät ole vierekkäin, ja vaihtaa ne keskenään. Tehtäväsi on järjestää listan alkiot pienimmästä suurimpaan käyttäen enintään $5n$ siirtoa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $t$: testien määrä.

Tämän jälkeen tulee $2t$ riviä, jotka kuvaavat testit. Jokaisessa testissä ensimmäisellä rivillä on kokonaisluku $n$ ja toisella rivillä on listan sisältö.

Tuloste

Tulosta jokaisessa testissä ensin siirtojen määrä $k$ ja sitten $k$ riviä, jotka kuvaavat siirrot. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: kohdissa $a$ ja $b$ olevat alkiot vaihdetaan keskenään.

Voit tulostaa jokaisessa testissä minkä tahansa kelvollisen ratkaisun. Jos ratkaisua ei ole olemassa, tulosta vain $-1$.

Esimerkki

Syöte:

4
2
1 2
5
5 4 3 2 1
3
2 1 3
4
2 4 3 1

Tuloste:

0
2
1 5
2 4
-1
2
1 4
2 4

Osatehtävä 1 (35 pistettä)

• $1 \le t \le 1000$
• $1 \le n \le 10$

Osatehtävä 2 (65 pistettä)

• $1 \le t \le 1000$
• $1 \le n \le 100$