ご存知の通り、あなたは中国構築問題コンテスト（Chinese Constructive Problem Contest, CCPC）に参加しており、出題校である「構築の王国」こと中山大学は、関連する問題にあなたが挑戦することを大いに期待しています。

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 は授業でこの問題を十分に良い時間計算量で解く方法を学びましたが、構築の王国の学生として、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 はすでに授業で学んだアルゴリズムを使ってチェッカーを実装しており、あなたがすべきことはこの構築問題を解くことです。

入力

この問題は複数のテストケースを含みます。入力の最初の行には、テストケースの個数を表す整数 $T$（$1 \le T \le 500$）が含まれます。

各テストケースについて、入力は整数 $X$（$1 \le X \le 10^9$）が書かれた単一の行からなります。その意味は問題文中で与えられた通りです。

出力

各テストケースについて、まず構築した数列の長さを表す整数 $l$（$3 \le l \le 6$）を1行に出力してください。次に、構築した数列を表す $l$ 個の整数を1行に出力してください。

任意の入力 $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$ の3つの行列の連鎖乗算を行う必要があることを表しています。次の2つの乗算戦略を考えます：

• まず $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$ となります。