Som du vet deltar du i Chinese Constructive Problem Contest (CCPC), och utan tvekan är det arrangerande lärosätet, Sun Yat-sen-universitetet, i egenskap av Konstruktionens Kungarike, mycket angeläget om att du ska anta några relaterade utmaningar.

Lilla U är student i Konstruktionens Kungarike. På en algoritmföreläsning lärde sig Lilla U om MCOP (Matrix Chain Ordering Problem). Här är en introduktion till MCOP:

Givet en följd av positiva heltal med längd $n \ge 3$, $[w_1, w_2, \dots, w_n]$, som indata till algoritmen. Följande formel multiplicerar $n - 1$ matriser för att slutligen erhålla en ny matris:

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

där $M_i$ är en matris av storlek $w_i \times w_{i+1}$. Matrismultiplikation uppfyller den associativa lagen, så att ändra multiplikationsordningen ger samma slutmatris $M$, men antalet operationer kan variera. Målet med problemet är att hitta en optimal multiplikationsstrategi bland $(n - 2)!$ möjliga strategier, så att det totala antalet operationer som krävs för matrismultiplikationen minimeras. Här antas att multiplikation av matriser av storlekarna $p \times q$ och $q \times r$ ger en matris av storlek $p \times r$ och kräver $pqr$ operationer. Det minsta totala antalet operationer som krävs för att beräkna $M$ under den optimala strategin betecknas med $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Lilla U har lärt sig hur man löser detta problem med tillräckligt bra tidskomplexitet på lektionen, men som student i Konstruktionens Kungarike kom Lilla U naturligtvis att tänka på följande problem:

Givet ett heltal $X$ som uppfyller $1 \le X \le 10^9$. Du ska konstruera en heltalsföljd av längd $l$, $[a_1, a_2, \dots, a_l]$, som uppfyller följande krav:

• $3 \le l \le 6$;
• För alla $i \in [1, l]$ gäller $1 \le a_i \le 4000$;
• $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.

Lilla U har redan implementerat en rättare (checker) med hjälp av algoritmen från lektionen, och det du behöver göra är att lösa detta konstruktionsproblem.

Indata

Detta problem innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 500$), som representerar antalet testfall.

För varje testfall består indatan av en enda rad med ett heltal $X$ ($1 \le X \le 10^9$), vars betydelse har angivits i problemtexten.

Utdata

För varje testfall: skriv först ut en rad med ett heltal $l$ ($3 \le l \le 6$), som representerar längden på den konstruerade följden. Skriv sedan ut en rad med $l$ heltal, som representerar den konstruerade följden.

Det kan bevisas att det för varje indata $X$ alltid finns en konstruktion som uppfyller kraven. Om det finns flera konstruktioner som uppfyller kraven, skriv ut vilken som helst av dem.

Exempel

Exempelindata 1

2
90
10

Exempelutdata 1

4
5 3 2 6
3
1 1 10

Notera

För det första testfallet är den konstruerade följden $[5, 3, 2, 6]$, vilket representerar behovet av att utföra en kedjemultiplikation av tre matriser med storlekarna $5 \times 3$, $3 \times 2$ och $2 \times 6$. Betrakta två multiplikationsstrategier:

• Multiplicera först $M_1$ och $M_2$ för att få en matris av storlek $5 \times 2$, och multiplicera sedan med $M_3$, vilket motsvarar uttrycket $(M_1 \times M_2) \times M_3$. Det totala antalet operationer är då $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Multiplicera först $M_2$ och $M_3$ för att få en matris av storlek $3 \times 6$, och multiplicera sedan med $M_1$, vilket motsvarar uttrycket $M_1 \times (M_2 \times M_3)$. Det totala antalet operationer är då $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Här är målet att minimera det totala antalet operationer, så $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.