Como sabes, estás participando en el Concurso Chino de Problemas Constructivos (Chinese Constructive Problem Contest, CCPC) y, sin lugar a dudas, la universidad organizadora, la Universidad Sun Yat-sen, como Reino de la Construcción, tiene muchas ganas de que te enfrentes a algunos problemas relacionados.
Little U es un estudiante del Reino de la Construcción. En una clase de algoritmos, Little U aprendió sobre el MCOP (Matrix Chain Ordering Problem, o problema de ordenación de cadenas de matrices). Aquí tienes una introducción al MCOP:
Dada una secuencia de enteros positivos de longitud $n \ge 3$, $[w_1, w_2, \dots, w_n]$, como entrada del algoritmo, la siguiente fórmula multiplica $n - 1$ matrices para obtener finalmente una nueva matriz:
$$M = M_1 \times M_2 \times \cdots \times M_{n-1}$$
donde $M_i$ es una matriz de tamaño $w_i \times w_{i+1}$. La multiplicación de matrices cumple la propiedad asociativa, por lo que cambiar el orden de multiplicación producirá la misma matriz final $M$, pero el número de operaciones puede variar. El objetivo del problema es encontrar una estrategia de multiplicación óptima entre las $(n - 2)!$ estrategias posibles, de modo que se minimice el número total de operaciones necesarias para la multiplicación de matrices. Aquí se asume que multiplicar matrices de tamaños $p \times q$ y $q \times r$ dará como resultado una matriz de tamaño $p \times r$, requiriendo $pqr$ operaciones. El número total mínimo de operaciones necesarias para calcular $M$ bajo la estrategia óptima se denota como $\text{MCOP}([w_1, w_2, \dots, w_n])$.
Little U ha aprendido en clase cómo resolver este problema con una complejidad temporal suficientemente buena, pero como estudiante del Reino de la Construcción, a Little U se le ocurrió naturalmente el siguiente problema:
Dado un entero $X$ que satisface $1 \le X \le 10^9$, debes construir una secuencia de enteros de longitud $l$, $[a_1, a_2, \dots, a_l]$, que cumpla los siguientes requisitos:
- $3 \le l \le 6$;
- Para todo $i \in [1, l]$, $1 \le a_i \le 4000$;
- $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.
Little U ya ha implementado un verificador (checker) utilizando el algoritmo aprendido en clase, y lo que tú debes hacer es resolver este problema de construcción.
Entrada
Este problema contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 500$), que representa el número de casos de prueba.
Para cada caso de prueba, la entrada consta de una sola línea con un entero $X$ ($1 \le X \le 10^9$), cuyo significado se ha explicado en el enunciado.
Salida
Para cada caso de prueba: primero imprime una línea con un entero $l$ ($3 \le l \le 6$), que representa la longitud de la secuencia construida. Luego imprime una línea con $l$ enteros, que representan la secuencia construida.
Se puede demostrar que para cualquier entrada $X$, siempre existe una construcción que cumple los requisitos. Si hay múltiples construcciones que cumplen los requisitos, imprime cualquiera de ellas.
Ejemplo
Entrada de ejemplo 1
2 90 10
Salida de ejemplo 1
4 5 3 2 6 3 1 1 10
Nota
Para el primer caso de prueba, la secuencia construida es $[5, 3, 2, 6]$, lo que representa la necesidad de realizar una multiplicación en cadena de tres matrices de tamaños $5 \times 3$, $3 \times 2$ y $2 \times 6$. Consideremos dos estrategias de multiplicación:
- Primero, multiplicar $M_1$ y $M_2$ para obtener una matriz de tamaño $5 \times 2$, y luego multiplicar por $M_3$, lo que corresponde a la expresión $(M_1 \times M_2) \times M_3$. El número total de operaciones en este caso es $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
- Primero, multiplicar $M_2$ y $M_3$ para obtener una matriz de tamaño $3 \times 6$, y luego multiplicar por $M_1$, lo que corresponde a la expresión $M_1 \times (M_2 \times M_3)$. El número total de operaciones en este caso es $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.
Aquí el objetivo es minimizar el número total de operaciones, por lo que $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.