Som du vet, deltar du i Chinese Constructive Problem Contest (CCPC), og uten tvil er det oppgaveforfattende universitetet, Sun Yat-sen-universitetet, som Konstruksjonens Kongerike, svært ivrig etter at du skal bryne deg på noen relaterte oppgaver.

Lille U er student i Konstruksjonens Kongerike. I en algoritmetime lærte Lille U om MCOP (Matrix Chain Ordering Problem). Her er en introduksjon til MCOP:

Gitt en følge av positive heltall med lengde $n \ge 3$, $[w_1, w_2, \dots, w_n]$, som inndata til algoritmen. Følgende formel multipliserer $n - 1$ matriser for til slutt å oppnå en ny matrise:

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

der $M_i$ er en matrise av størrelse $w_i \times w_{i+1}$. Matrisemultiplikasjon oppfyller den assosiative loven, så å endre multiplikasjonsrekkefølgen vil gi den samme sluttmatrisen $M$, men antallet operasjoner kan variere. Målet med problemet er å finne en optimal multiplikasjonsstrategi blant $(n - 2)!$ mulige strategier, slik at det totale antallet operasjoner som kreves for matrisemultiplikasjonen minimeres. Her antas det at å multiplisere matriser av størrelsene $p \times q$ og $q \times r$ vil gi en matrise av størrelse $p \times r$, og kreve $pqr$ operasjoner. Det minimale totale antallet operasjoner som kreves for å beregne $M$ under den optimale strategien betegnes som $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Lille U har lært hvordan man løser dette problemet med tilstrekkelig god tidskompleksitet i timen, men som student i Konstruksjonens Kongerike tenkte Lille U naturligvis på følgende problem:

Gitt et heltall $X$ som oppfyller $1 \le X \le 10^9$. Du må konstruere en heltallsfølge med lengde $l$, $[a_1, a_2, \dots, a_l]$, som oppfyller følgende krav:

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

Lille U har allerede implementert en sjekker (checker) ved hjelp av algoritmen fra timen, og det du må gjøre er å løse dette konstruksjonsproblemet.

Inndata

Denne oppgaven inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 500$), som representerer antallet testtilfeller.

For hvert testtilfelle består inndataene av én enkelt linje med et heltall $X$ ($1 \le X \le 10^9$), hvis betydning er gitt i oppgaveteksten.

Utdata

For hvert testtilfelle: skriv først ut en linje med et heltall $l$ ($3 \le l \le 6$), som representerer lengden på den konstruerte følgen. Skriv deretter ut en linje med $l$ heltall, som representerer den konstruerte følgen.

Det kan bevises at det for enhver inndata $X$ alltid finnes en konstruksjon som oppfyller kravene. Hvis det finnes flere konstruksjoner som oppfyller kravene, kan du skrive ut hvilken som helst av dem.

Eksempel

Eksempelinndata 1

2
90
10

Eksempelutdata 1

4
5 3 2 6
3
1 1 10

Merk

For det første testtilfellet er den konstruerte følgen $[5, 3, 2, 6]$, som representerer behovet for å utføre en kjedemultiplikasjon av tre matriser med størrelsene $5 \times 3$, $3 \times 2$ og $2 \times 6$. Betrakt to multiplikasjonsstrategier:

• Multipliser først $M_1$ og $M_2$ for å få en matrise av størrelse $5 \times 2$, og multipliser deretter med $M_3$, som tilsvarer uttrykket $(M_1 \times M_2) \times M_3$. Det totale antallet operasjoner er da $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Multipliser først $M_2$ og $M_3$ for å få en matrise av størrelse $3 \times 6$, og multipliser deretter med $M_1$, som tilsvarer uttrykket $M_1 \times (M_2 \times M_3)$. Det totale antallet operasjoner er da $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Her er målet å minimere det totale antallet operasjoner, så $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.