Kuten tiedät, osallistut Kiinan konstruktiivisten tehtävien kilpailuun (Chinese Constructive Problem Contest, CCPC), ja epäilemättä tehtävät laatinut yliopisto, Sun Yat-senin yliopisto, Konstruktion Kuningaskuntana odottaa innolla, että haastat itsesi muutaman aiheeseen liittyvän tehtävän parissa.

Pikku U on opiskelija Konstruktion Kuningaskunnassa. Algoritmikurssilla Pikku U oppi MCOP-ongelmasta (Matrix Chain Ordering Problem, matriisiketjun kertomisjärjestysongelma). Tässä on johdanto MCOP-ongelmaan:

Algoritmin syötteenä annetaan positiivisten kokonaislukujen jono, jonka pituus on $n \ge 3$: $[w_1, w_2, \dots, w_n]$. Seuraava kaava kertoo $n - 1$ matriisia keskenään tuottaen lopulta uuden matriisin:

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

missä $M_i$ on kokoluokan $w_i \times w_{i+1}$ matriisi. Matriisikertolasku noudattaa liitäntälakia, joten kertomisjärjestyksen muuttaminen tuottaa saman lopullisen matriisin $M$, mutta laskutoimitusten määrä voi vaihdella. Ongelman tavoitteena on löytää $(n - 2)!$ mahdollisen strategian joukosta optimaalinen kertomisstrategia siten, että matriisikertolaskuun tarvittavien laskutoimitusten kokonaismäärä minimoituu. Tässä oletetaan, että kokoa $p \times q$ ja $q \times r$ olevien matriisien kertominen tuottaa kokoa $p \times r$ olevan matriisin ja vaatii $pqr$ laskutoimitusta. Pienintä kokonaislaskutoimitusten määrää, joka tarvitaan matriisin $M$ laskemiseen optimaalisella strategialla, merkitään $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Pikku U on oppinut kurssilla, kuinka tämä ongelma ratkaistaan riittävän hyvällä aikavaativuudella, mutta Konstruktion Kuningaskunnan opiskelijana Pikku U keksi luonnollisesti seuraavan tehtävän:

Annettuna on kokonaisluku $X$, joka toteuttaa ehdon $1 \le X \le 10^9$. Sinun tulee muodostaa pituuden $l$ kokonaislukujono $[a_1, a_2, \dots, a_l]$, joka täyttää seuraavat vaatimukset:

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

Pikku U on jo toteuttanut tarkistimen (checker) käyttäen kurssilla oppimaansa algoritmia, ja sinun tehtäväsi on ratkaista tämä konstruktiotehtävä.

Syöte

Tässä tehtävässä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 500$), joka ilmoittaa testitapausten lukumäärän.

Jokaiselle testitapaukselle syöte koostuu yhdestä rivistä, jolla on kokonaisluku $X$ ($1 \le X \le 10^9$), jonka merkitys on kerrottu tehtävänannossa.

Tuloste

Jokaiselle testitapaukselle: tulosta ensin rivi, jolla on kokonaisluku $l$ ($3 \le l \le 6$), joka ilmoittaa muodostetun jonon pituuden. Tulosta sitten rivi, jolla on $l$ kokonaislukua, jotka esittävät muodostetun jonon.

Voidaan todistaa, että mille tahansa syötteelle $X$ on aina olemassa vaatimukset täyttävä konstruktio. Jos vaatimukset täyttäviä konstruktioita on useita, tulosta mikä tahansa niistä.

Esimerkki

Esimerkkisyöte 1

2
90
10

Esimerkkituloste 1

4
5 3 2 6
3
1 1 10

Huomautus

Ensimmäisessä testitapauksessa muodostettu jono on $[5, 3, 2, 6]$, mikä tarkoittaa kolmen kokoa $5 \times 3$, $3 \times 2$ ja $2 \times 6$ olevan matriisin ketjukertolaskua. Tarkastellaan kahta kertomisstrategiaa:

• Kerrotaan ensin $M_1$ ja $M_2$, jolloin saadaan kokoa $5 \times 2$ oleva matriisi, ja kerrotaan se sitten matriisilla $M_3$, mikä vastaa lauseketta $(M_1 \times M_2) \times M_3$. Laskutoimitusten kokonaismäärä on tällöin $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Kerrotaan ensin $M_2$ ja $M_3$, jolloin saadaan kokoa $3 \times 6$ oleva matriisi, ja kerrotaan se sitten matriisilla $M_1$, mikä vastaa lauseketta $M_1 \times (M_2 \times M_3)$. Laskutoimitusten kokonaismäärä on tällöin $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Tässä tavoitteena on minimoida laskutoimitusten kokonaismäärä, joten $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.