Как вы знаете, вы участвуете в Китайском соревновании по конструктивным задачам (Chinese Constructive Problem Contest, CCPC), и, без сомнения, университет-составитель — Университет Сунь Ятсена, будучи Королевством Конструктива, очень ждёт, что вы бросите вызов нескольким связанным с этим задачам.

Маленький U — студент Королевства Конструктива. На занятии по алгоритмам Маленький U узнал о задаче MCOP (Matrix Chain Ordering Problem — задача о порядке перемножения матриц). Вот краткое описание MCOP:

На вход алгоритму подаётся последовательность положительных целых чисел длины $n \ge 3$: $[w_1, w_2, \dots, w_n]$. Следующая формула перемножает $n - 1$ матриц, чтобы в итоге получить новую матрицу:

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

где $M_i$ — матрица размера $w_i \times w_{i+1}$. Умножение матриц ассоциативно, поэтому изменение порядка умножения приведёт к той же итоговой матрице $M$, однако количество операций может отличаться. Цель задачи — найти оптимальную стратегию умножения среди $(n - 2)!$ возможных стратегий, при которой общее количество операций, необходимых для перемножения матриц, минимально. Здесь предполагается, что умножение матриц размеров $p \times q$ и $q \times r$ даёт матрицу размера $p \times r$ и требует $pqr$ операций. Минимальное общее количество операций, необходимое для вычисления $M$ при оптимальной стратегии, обозначается как $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Маленький U уже научился на занятии решать эту задачу с достаточно хорошей временной сложностью, но, как студент Королевства Конструктива, он естественным образом задумался о следующей задаче:

Дано целое число $X$, удовлетворяющее условию $1 \le X \le 10^9$. Вам необходимо построить последовательность целых чисел длины $l$, $[a_1, a_2, \dots, a_l]$, удовлетворяющую следующим требованиям:

• $3 \le l \le 6$;
• Для всех $i \in [1, l]$ выполняется $1 \le a_i \le 4000$;
• $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.

Маленький U уже реализовал проверяющую программу (checker) с помощью изученного на занятии алгоритма, а вам нужно решить эту конструктивную задачу.

Входные данные

Эта задача содержит несколько наборов входных данных. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 500$), обозначающее количество наборов входных данных.

Для каждого набора входных данных вход состоит из одной строки, содержащей целое число $X$ ($1 \le X \le 10^9$), смысл которого описан в условии задачи.

Выходные данные

Для каждого набора входных данных: сначала выведите строку с целым числом $l$ ($3 \le l \le 6$), обозначающим длину построенной последовательности. Затем выведите строку с $l$ целыми числами, описывающими построенную последовательность.

Можно доказать, что для любого входного числа $X$ всегда существует построение, удовлетворяющее требованиям. Если подходящих построений несколько, выведите любое из них.

Пример

Пример входных данных 1

2
90
10

Пример выходных данных 1

4
5 3 2 6
3
1 1 10

Примечание

В первом наборе входных данных построенная последовательность равна $[5, 3, 2, 6]$, что означает необходимость выполнить цепочечное перемножение трёх матриц размеров $5 \times 3$, $3 \times 2$ и $2 \times 6$. Рассмотрим две стратегии умножения:

• Сначала перемножить $M_1$ и $M_2$, получив матрицу размера $5 \times 2$, а затем умножить на $M_3$, что соответствует выражению $(M_1 \times M_2) \times M_3$. Общее число операций в этом случае равно $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Сначала перемножить $M_2$ и $M_3$, получив матрицу размера $3 \times 6$, а затем умножить слева на $M_1$, что соответствует выражению $M_1 \times (M_2 \times M_3)$. Общее число операций в этом случае равно $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Поскольку цель состоит в минимизации общего числа операций, получаем $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.