Pada tahun 2077, pembuatan soal menjadi sederhana. Robot akan membuat soal dengan menetapkan beberapa operasi acak lalu menyelesaikannya sendiri. Pembuat soal hanya perlu memeriksa apakah soal tersebut benar atau tidak.

Berikut adalah sebuah soal dari tahun 2077:

Diberikan sebuah permutasi $p_1, p_2, \dots, p_n$, dijamin bahwa $n$ adalah bilangan genap. Anda ingin mengurutkan permutasi tersebut hanya dengan menggunakan satu jenis operasi:

• FakeSort(l,r): Anda harus menjamin bahwa $r - l + 1$ adalah genap. Misalkan $k = r - l + 1$, maka $k/2$ elemen terbesar dan $k/2$ elemen terkecil dalam subbarisan kontinu $p_l, p_{l+1}, \dots, p_r$ akan diurutkan secara independen. Artinya, misalkan $L_1, L_2, \dots, L_{k/2}$ adalah indeks dari $k/2$ bilangan terbesar, dan $S_1, S_2, \dots, S_{k/2}$ adalah indeks dari $k/2$ bilangan terkecil. Pertama-tama kita mengurutkan bilangan-bilangan pada indeks $L_1 \sim L_{k/2}$, kemudian mengurutkan bilangan-bilangan pada indeks $S_1 \sim S_{k/2}$.

Berikut adalah contoh konkret; misalkan permutasinya adalah $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Jika kita memanggil FakeSort(2,7):

• $k = r - l + 1 = 6$. Subbarisan kontinu $p_l, p_{l+1}, \dots, p_r$ adalah $\{5, 7, 1, 8, 6, 4\}$; kita akan mengurutkan $3$ bilangan terbesar dan $3$ bilangan terkecil dari barisan ini secara independen.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; $3$ bilangan terbesar dicetak tebal. Setelah diurutkan, hasilnya menjadi $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; $3$ bilangan terkecil dicetak tebal. Setelah diurutkan, hasilnya menjadi $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Jadi $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ setelah FakeSort(2,7) menjadi $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Gunakan paling banyak $114$ operasi untuk mengurutkan permutasi tersebut atau tentukan bahwa hal itu tidak mungkin. Dapat dibuktikan bahwa jika suatu permutasi dapat diurutkan dengan operasi ini, pasti ada cara yang menggunakan paling banyak $114$ operasi.

Masukan

Masukan terdiri dari beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^3$), yaitu banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat genap $n$ ($4 \le n \le 10^5$), yaitu panjang permutasi.

Baris kedua berisi $n$ bilangan bulat $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), yaitu permutasi yang perlu Anda urutkan. Dijamin bahwa $p$ adalah sebuah permutasi.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, jika tidak mungkin mengurutkan permutasi tersebut, cetak $-1$.

Jika mungkin, cetak sebuah bilangan bulat $k$ ($0 \le k \le 114$), yang menyatakan banyaknya operasi yang digunakan.

Pada $k$ baris berikutnya, cetak $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ genap) pada setiap baris, yang menyatakan pelaksanaan FakeSort(l,r).

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

1
1 4
-1
2
4 7
1 6