Як ви знаєте, ви берете участь у Китайському змаганні з конструктивних задач (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$.