Wie du weißt, nimmst du am Chinese Constructive Problem Contest (CCPC) teil, und zweifellos ist die aufgabenstellende Universität, die Sun-Yat-sen-Universität, als das Königreich der Konstruktion sehr gespannt darauf, dass du dich einigen einschlägigen Aufgaben stellst.

Little U ist Student im Königreich der Konstruktion. In einer Algorithmenvorlesung hat Little U das MCOP (Matrix Chain Ordering Problem, Matrizenkettenmultiplikationsproblem) kennengelernt. Hier ist eine Einführung in MCOP:

Gegeben sei eine Folge positiver ganzer Zahlen der Länge $n \ge 3$, $[w_1, w_2, \dots, w_n]$, als Eingabe für den Algorithmus. Die folgende Formel multipliziert $n - 1$ Matrizen, um schließlich eine neue Matrix zu erhalten:

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

wobei $M_i$ eine Matrix der Größe $w_i \times w_{i+1}$ ist. Die Matrizenmultiplikation erfüllt das Assoziativgesetz, sodass eine Änderung der Multiplikationsreihenfolge dieselbe Endmatrix $M$ liefert, sich die Anzahl der Operationen jedoch unterscheiden kann. Ziel des Problems ist es, unter $(n - 2)!$ möglichen Strategien eine optimale Multiplikationsstrategie zu finden, sodass die Gesamtzahl der für die Matrizenmultiplikation erforderlichen Operationen minimiert wird. Hierbei wird angenommen, dass die Multiplikation von Matrizen der Größen $p \times q$ und $q \times r$ eine Matrix der Größe $p \times r$ ergibt und $pqr$ Operationen erfordert. Die minimale Gesamtzahl von Operationen, die zur Berechnung von $M$ unter der optimalen Strategie erforderlich ist, wird mit $\text{MCOP}([w_1, w_2, \dots, w_n])$ bezeichnet.

Little U hat im Unterricht gelernt, wie man dieses Problem mit hinreichend guter Zeitkomplexität löst, aber als Student des Königreichs der Konstruktion kam Little U natürlich auf das folgende Problem:

Gegeben ist eine ganze Zahl $X$ mit $1 \le X \le 10^9$. Du musst eine ganzzahlige Folge der Länge $l$, $[a_1, a_2, \dots, a_l]$, konstruieren, die die folgenden Anforderungen erfüllt:

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

Little U hat bereits mithilfe des im Unterricht gelernten Algorithmus einen Checker implementiert, und deine Aufgabe besteht nun darin, dieses Konstruktionsproblem zu lösen.

Eingabe

Dieses Problem enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 500$), die die Anzahl der Testfälle angibt.

Für jeden Testfall besteht die Eingabe aus einer einzelnen Zeile mit einer ganzen Zahl $X$ ($1 \le X \le 10^9$), deren Bedeutung in der Aufgabenstellung beschrieben wurde.

Ausgabe

Für jeden Testfall: Gib zunächst eine Zeile mit einer ganzen Zahl $l$ ($3 \le l \le 6$) aus, die die Länge der konstruierten Folge angibt. Gib anschließend eine Zeile mit $l$ ganzen Zahlen aus, die die konstruierte Folge darstellen.

Es lässt sich beweisen, dass es für jede Eingabe $X$ immer eine Konstruktion gibt, die die Anforderungen erfüllt. Falls es mehrere solcher Konstruktionen gibt, gib eine beliebige davon aus.

Beispiel

Beispieleingabe 1

2
90
10

Beispielausgabe 1

4
5 3 2 6
3
1 1 10

Hinweis

Für den ersten Testfall lautet die konstruierte Folge $[5, 3, 2, 6]$, was bedeutet, dass eine Kettenmultiplikation von drei Matrizen der Größen $5 \times 3$, $3 \times 2$ und $2 \times 6$ durchgeführt werden muss. Betrachte zwei Multiplikationsstrategien:

• Multipliziere zuerst $M_1$ und $M_2$, um eine Matrix der Größe $5 \times 2$ zu erhalten, und multipliziere diese dann mit $M_3$, was dem Ausdruck $(M_1 \times M_2) \times M_3$ entspricht. Die Gesamtzahl der Operationen beträgt hierbei $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Multipliziere zuerst $M_2$ und $M_3$, um eine Matrix der Größe $3 \times 6$ zu erhalten, und multipliziere diese dann mit $M_1$, was dem Ausdruck $M_1 \times (M_2 \times M_3)$ entspricht. Die Gesamtzahl der Operationen beträgt hierbei $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Da das Ziel darin besteht, die Gesamtzahl der Operationen zu minimieren, gilt $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.