Seperti yang Anda ketahui, Anda sedang berpartisipasi dalam Chinese Constructive Problem Contest (CCPC), dan tanpa ragu lagi, universitas pembuat soal, Sun Yat-sen University, sebagai Kerajaan Konstruksi, sangat antusias agar Anda menaklukkan beberapa soal terkait.

Little U adalah seorang mahasiswa di Kerajaan Konstruksi. Dalam kelas algoritma, Little U mempelajari MCOP (Matrix Chain Ordering Problem). Berikut adalah pengantar mengenai MCOP:

Diberikan sebuah barisan bilangan bulat positif dengan panjang $n \ge 3$, $[w_1, w_2, \dots, w_n]$, sebagai masukan untuk algoritma. Rumus berikut mengalikan $n - 1$ matriks untuk pada akhirnya memperoleh sebuah matriks baru:

$$M = M_1 \times M_2 \times \cdots \times M_{n-1}$$

dengan $M_i$ adalah matriks berukuran $w_i \times w_{i+1}$. Perkalian matriks memenuhi sifat asosiatif, sehingga mengubah urutan perkalian akan menghasilkan matriks akhir $M$ yang sama, tetapi banyaknya operasi dapat berbeda. Tujuan dari masalah ini adalah mencari strategi perkalian optimal di antara $(n - 2)!$ strategi yang mungkin, sedemikian sehingga total banyaknya operasi yang diperlukan untuk perkalian matriks menjadi minimum. Di sini, diasumsikan bahwa mengalikan matriks berukuran $p \times q$ dan $q \times r$ akan menghasilkan matriks berukuran $p \times r$, yang memerlukan $pqr$ operasi. Total banyaknya operasi minimum yang diperlukan untuk menghitung $M$ di bawah strategi optimal dinotasikan sebagai $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Little U telah mempelajari cara menyelesaikan masalah ini dengan kompleksitas waktu yang cukup baik di kelas, tetapi sebagai mahasiswa Kerajaan Konstruksi, Little U secara alami memikirkan masalah berikut:

Diberikan sebuah bilangan bulat $X$, yang memenuhi $1 \le X \le 10^9$. Anda perlu mengonstruksi sebuah barisan bilangan bulat dengan panjang $l$, $[a_1, a_2, \dots, a_l]$, yang memenuhi persyaratan berikut:

• $3 \le l \le 6$;
• Untuk semua $i \in [1, l]$, $1 \le a_i \le 4000$;
• $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.

Little U telah mengimplementasikan pemeriksa (checker) menggunakan algoritma yang dipelajari di kelas, dan yang perlu Anda lakukan adalah menyelesaikan masalah konstruksi ini.

Masukan

Soal ini memuat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 500$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, masukan terdiri dari satu baris tunggal berisi sebuah bilangan bulat $X$ ($1 \le X \le 10^9$), yang maknanya telah diberikan pada soal.

Keluaran

Untuk setiap kasus uji: pertama keluarkan satu baris berisi sebuah bilangan bulat $l$ ($3 \le l \le 6$), yang menyatakan panjang barisan yang dikonstruksi. Kemudian keluarkan satu baris berisi $l$ bilangan bulat, yang menyatakan barisan yang dikonstruksi.

Dapat dibuktikan bahwa untuk sembarang masukan $X$, selalu ada konstruksi yang memenuhi persyaratan. Jika terdapat beberapa konstruksi yang memenuhi persyaratan, keluarkan salah satu saja di antaranya.

Contoh

Contoh Masukan 1

2
90
10

Contoh Keluaran 1

4
5 3 2 6
3
1 1 10

Catatan

Untuk kasus uji pertama, barisan yang dikonstruksi adalah $[5, 3, 2, 6]$, yang menyatakan perlunya melakukan perkalian berantai dari tiga matriks berukuran $5 \times 3$, $3 \times 2$, dan $2 \times 6$. Tinjuau dua strategi perkalian:

• Pertama, kalikan $M_1$ dan $M_2$ untuk memperoleh matriks berukuran $5 \times 2$, lalu kalikan dengan $M_3$, yang bersesuaian dengan ekspresi $(M_1 \times M_2) \times M_3$. Total banyaknya operasi pada cara ini adalah $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Pertama, kalikan $M_2$ dan $M_3$ untuk memperoleh matriks berukuran $3 \times 6$, lalu kalikan dengan $M_1$, yang bersesuaian dengan ekspresi $M_1 \times (M_2 \times M_3)$. Total banyaknya operasi pada cara ini adalah $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Di sini, tujuannya adalah meminimalkan total banyaknya operasi, sehingga $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.