眾所周知，你而家參加緊中國構造題競賽（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 喺堂上面已經學識咗點樣用足夠好嘅時間複雜度去解決呢個問題，但作為構造王國嘅學生，小 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$。