Little Cyan Fish memiliki sebuah permutasi $p_1, p_2, \ldots, p_n$ dari bilangan bulat dari $1$ hingga $n$, dan, seperti yang disiratkan oleh judul soal ini, ia ingin mengurutkannya dalam urutan menaik. Kali ini, operasi yang dapat ia lakukan adalah sebagai berikut.

• Dalam satu operasi, Little Cyan Fish dapat memilih dua bilangan bulat $i$ dan $j$ sedemikian sehingga $1 \le i < j \le n$ lalu menukar $p_i$ dan $p_j$.

Namun, ayolah, semua orang tahu cara mengurutkan permutasi dengan pertukaran sederhana, jadi jelas bukan itu yang diminta oleh soal ini. Sebagai gantinya, Little Cyan Fish mendefinisikan jarak dari suatu operasi sebagai $j - i$. Untuk suatu barisan operasi yang mengurutkan permutasi tersebut, misalkan $a_d$ menyatakan banyaknya operasi berjarak $d$, untuk setiap $1 \le d < n$.

Di antara semua barisan operasi berhingga yang mengurutkan permutasi tersebut, Little Cyan Fish ingin Anda mencari barisan $(a_1, a_2, \ldots, a_{n-1})$ yang terkecil secara leksikografis, serta mengonstruksi suatu barisan yang terdiri dari paling banyak $5n$ operasi yang mencapainya.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^6$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($2 \le n \le 10^6$), yang menyatakan panjang permutasi. Baris kedua berisi $n$ bilangan bulat $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), yang menyatakan permutasi tersebut. Dijamin bahwa $p$ adalah permutasi dengan panjang $n$.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan jawaban dalam format berikut.

Baris pertama untuk setiap kasus uji harus berisi $n - 1$ bilangan bulat $a_1, a_2, \ldots, a_{n-1}$, yaitu barisan terkecil secara leksikografis.

Baris kedua harus berisi sebuah bilangan bulat $k$ ($0 \le k \le 5n$), yaitu banyaknya operasi dalam barisan Anda.

Masing-masing dari $k$ baris berikutnya harus berisi dua bilangan bulat $i$ dan $j$ ($1 \le i < j \le n$), yaitu indeks-indeks yang dipilih pada operasi yang bersangkutan. Operasi-operasi tersebut, ketika dijalankan sesuai urutan yang diberikan, harus mengurutkan permutasi masukan, dan untuk setiap $1 \le d < n$, tepat $a_d$ dari operasi-operasi tersebut harus memiliki jarak $d$.

Dapat dibuktikan bahwa barisan optimal dengan paling banyak $5n$ operasi selalu ada. Jika terdapat beberapa barisan operasi yang valid, Anda boleh mengeluarkan yang mana saja.

Contoh

Masukan 1

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

Keluaran 1

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

Catatan

Pada kasus uji contoh pertama, Little Cyan Fish menukar posisi $1$ dan $3$. Ini mengurutkan permutasi menggunakan satu operasi berjarak $2$.

Pada kasus uji contoh kedua, salah satu barisan optimal adalah $(1, 4)$, $(2, 4)$, $(1, 4)$. Jarak-jaraknya adalah $3$, $2$, dan $3$, sehingga barisan yang dihasilkan adalah $(0, 1, 2)$.

Pada kasus uji contoh ketiga, salah satu barisan optimal adalah $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Banyaknya operasi untuk masing-masing jarak adalah $(0, 3, 2)$.