아시다시피 여러분은 중국 구성적 문제 경시대회(Chinese Constructive Problem Contest, CCPC)에 참가하고 있으며, 의심할 여지 없이 '구성의 왕국'이라 불리는 출제 학교 중산대학(Sun Yat-sen University)은 여러분이 관련 문제들에 도전하기를 매우 고대하고 있습니다.

Little U는 구성의 왕국의 학생입니다. 알고리즘 수업 시간에 Little 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])$으로 표기합니다.

Little U는 수업 시간에 이 문제를 충분히 좋은 시간 복잡도로 해결하는 방법을 배웠지만, 구성의 왕국의 학생답게 자연스럽게 다음과 같은 문제를 떠올렸습니다:

$1 \le X \le 10^9$을 만족하는 정수 $X$가 주어집니다. 다음 조건을 만족하는 길이 $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$.

Little 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$입니다.