Come sai, stai partecipando al Chinese Constructive Problem Contest (CCPC) e, senza dubbio, l'università proponente, la Sun Yat-sen University, in quanto Regno della Costruzione, è impaziente di vederti affrontare alcuni problemi correlati.

Little U è uno studente del Regno della Costruzione. Durante una lezione di algoritmi, Little U ha studiato il problema MCOP (Matrix Chain Ordering Problem). Ecco un'introduzione a MCOP:

Data una sequenza di interi positivi di lunghezza $n \ge 3$, $[w_1, w_2, \dots, w_n]$, come input dell'algoritmo, la seguente formula moltiplica $n - 1$ matrici per ottenere infine una nuova matrice:

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

dove $M_i$ è una matrice di dimensione $w_i \times w_{i+1}$. La moltiplicazione tra matrici soddisfa la proprietà associativa, quindi cambiando l'ordine di moltiplicazione si otterrà la stessa matrice finale $M$, ma il numero di operazioni può variare. L'obiettivo del problema è trovare una strategia di moltiplicazione ottimale tra le $(n - 2)!$ strategie possibili, in modo da minimizzare il numero totale di operazioni necessarie per la moltiplicazione delle matrici. Qui si assume che moltiplicare matrici di dimensioni $p \times q$ e $q \times r$ produca una matrice di dimensione $p \times r$, richiedendo $pqr$ operazioni. Il numero totale minimo di operazioni necessarie per calcolare $M$ secondo la strategia ottimale è indicato con $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Little U ha imparato a lezione come risolvere questo problema con una complessità temporale sufficientemente buona, ma come studente del Regno della Costruzione, Little U ha pensato naturalmente al seguente problema:

Dato un intero $X$ che soddisfa $1 \le X \le 10^9$, devi costruire una sequenza di interi di lunghezza $l$, $[a_1, a_2, \dots, a_l]$, che soddisfi i seguenti requisiti:

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

Little U ha già implementato un verificatore (checker) utilizzando l'algoritmo imparato a lezione, e ciò che devi fare è risolvere questo problema costruttivo.

Input

Questo problema contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 500$), che rappresenta il numero di casi di test.

Per ciascun caso di test, l'input è costituito da una singola riga con un intero $X$ ($1 \le X \le 10^9$), il cui significato è stato descritto nel problema.

Output

Per ciascun caso di test: stampa prima una riga con un intero $l$ ($3 \le l \le 6$), che rappresenta la lunghezza della sequenza costruita. Poi stampa una riga con $l$ interi, che rappresentano la sequenza costruita.

Si può dimostrare che per qualsiasi input $X$ esiste sempre una costruzione che soddisfa i requisiti. Se esistono più costruzioni che soddisfano i requisiti, stampane una qualsiasi.

Esempio

Input di esempio 1

2
90
10

Output di esempio 1

4
5 3 2 6
3
1 1 10

Nota

Per il primo caso di test, la sequenza costruita è $[5, 3, 2, 6]$, il che rappresenta la necessità di eseguire una moltiplicazione a catena di tre matrici di dimensioni $5 \times 3$, $3 \times 2$ e $2 \times 6$. Consideriamo due strategie di moltiplicazione:

• Moltiplicare prima $M_1$ e $M_2$ per ottenere una matrice di dimensione $5 \times 2$, e poi moltiplicare per $M_3$, il che corrisponde all'espressione $(M_1 \times M_2) \times M_3$. Il numero totale di operazioni in questo caso è $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Moltiplicare prima $M_2$ e $M_3$ per ottenere una matrice di dimensione $3 \times 6$, e poi moltiplicare per $M_1$, il che corrisponde all'espressione $M_1 \times (M_2 \times M_3)$. Il numero totale di operazioni in questo caso è $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Qui l'obiettivo è minimizzare il numero totale di operazioni, quindi $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.