Comme vous le savez, vous participez au Concours Chinois de Problèmes Constructifs (Chinese Constructive Problem Contest, CCPC), et sans aucun doute, l'université organisatrice, l'Université Sun Yat-sen, en tant que Royaume de la Construction, a très hâte de vous voir relever certains défis liés à ce thème.

Little U est étudiant au Royaume de la Construction. Lors d'un cours d'algorithmique, Little U a découvert le problème MCOP (Matrix Chain Ordering Problem, ou problème d'ordonnancement de chaînes de matrices). Voici une présentation de MCOP :

On donne en entrée de l'algorithme une suite d'entiers strictement positifs de longueur $n \ge 3$, $[w_1, w_2, \dots, w_n]$. La formule suivante multiplie $n - 1$ matrices pour obtenir finalement une nouvelle matrice :

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

où $M_i$ est une matrice de taille $w_i \times w_{i+1}$. La multiplication matricielle étant associative, changer l'ordre des multiplications donne la même matrice finale $M$, mais le nombre d'opérations peut varier. L'objectif du problème est de trouver une stratégie de multiplication optimale parmi les $(n - 2)!$ stratégies possibles, de sorte que le nombre total d'opérations nécessaires à la multiplication des matrices soit minimisé. On suppose ici que multiplier deux matrices de tailles $p \times q$ et $q \times r$ produit une matrice de taille $p \times r$ et nécessite $pqr$ opérations. Le nombre total minimal d'opérations requis pour calculer $M$ selon la stratégie optimale est noté $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Little U a appris en cours comment résoudre ce problème avec une complexité temporelle suffisamment bonne, mais en tant qu'étudiant du Royaume de la Construction, Little U a naturellement pensé au problème suivant :

Soit un entier $X$ vérifiant $1 \le X \le 10^9$. Vous devez construire une suite d'entiers de longueur $l$, $[a_1, a_2, \dots, a_l]$, qui respecte les conditions suivantes :

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

Little U a déjà implémenté un vérificateur (checker) à l'aide de l'algorithme vu en cours ; ce qu'il vous reste à faire est de résoudre ce problème de construction.

Entrée

Ce problème contient plusieurs jeux de tests. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 500$), représentant le nombre de jeux de tests.

Pour chaque jeu de tests, l'entrée consiste en une seule ligne contenant un entier $X$ ($1 \le X \le 10^9$), dont la signification a été donnée dans l'énoncé.

Sortie

Pour chaque jeu de tests : affichez d'abord une ligne contenant un entier $l$ ($3 \le l \le 6$), représentant la longueur de la suite construite. Puis affichez une ligne contenant $l$ entiers, représentant la suite construite.

On peut prouver que pour toute entrée $X$, il existe toujours une construction qui respecte les conditions. S'il existe plusieurs constructions valides, affichez n'importe laquelle d'entre elles.

Exemple

Entrée d'exemple 1

2
90
10

Sortie d'exemple 1

4
5 3 2 6
3
1 1 10

Remarque

Pour le premier jeu de tests, la suite construite est $[5, 3, 2, 6]$, ce qui représente la multiplication en chaîne de trois matrices de tailles $5 \times 3$, $3 \times 2$ et $2 \times 6$. Considérons deux stratégies de multiplication :

• Multiplier d'abord $M_1$ et $M_2$ pour obtenir une matrice de taille $5 \times 2$, puis multiplier par $M_3$, ce qui correspond à l'expression $(M_1 \times M_2) \times M_3$. Le nombre total d'opérations est alors $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$ ;
• Multiplier d'abord $M_2$ et $M_3$ pour obtenir une matrice de taille $3 \times 6$, puis multiplier par $M_1$, ce qui correspond à l'expression $M_1 \times (M_2 \times M_3)$. Le nombre total d'opérations est alors $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Ici, l'objectif est de minimiser le nombre total d'opérations, donc $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.