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