Như bạn đã biết, bạn đang tham gia Cuộc thi Bài toán Kiến tạo Trung Quốc (Chinese Constructive Problem Contest - CCPC), và không còn nghi ngờ gì nữa, trường ra đề — Đại học Trung Sơn, với tư cách là Vương quốc Kiến tạo — rất mong chờ bạn thử sức với một số bài toán liên quan.

Little U là một sinh viên tại Vương quốc Kiến tạo. Trong một giờ học thuật toán, Little U đã được học về bài toán MCOP (Bài toán Thứ tự Nhân Chuỗi Ma trận - Matrix Chain Ordering Problem). Dưới đây là phần giới thiệu về MCOP:

Cho một dãy số nguyên dương có độ dài $n \ge 3$, $[w_1, w_2, \dots, w_n]$, làm đầu vào cho thuật toán. Công thức dưới đây nhân $n - 1$ ma trận để cuối cùng thu được một ma trận mới:

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

trong đó $M_i$ là một ma trận có kích thước $w_i \times w_{i+1}$. Phép nhân ma trận có tính chất kết hợp, vì vậy việc thay đổi thứ tự nhân sẽ cho ra cùng một ma trận cuối cùng $M$, nhưng số phép toán có thể khác nhau. Mục tiêu của bài toán là tìm một chiến lược nhân tối ưu trong số $(n - 2)!$ chiến lược khả dĩ, sao cho tổng số phép toán cần thiết để nhân ma trận là nhỏ nhất. Ở đây, giả sử rằng việc nhân hai ma trận có kích thước $p \times q$ và $q \times r$ sẽ tạo ra một ma trận có kích thước $p \times r$, cần $pqr$ phép toán. Tổng số phép toán tối thiểu cần thiết để tính $M$ theo chiến lược tối ưu được ký hiệu là $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Little U đã học được cách giải bài toán này với độ phức tạp thời gian đủ tốt trên lớp, nhưng là một sinh viên của Vương quốc Kiến tạo, Little U tự nhiên nghĩ đến bài toán sau:

Cho một số nguyên $X$ thỏa mãn $1 \le X \le 10^9$. Bạn cần xây dựng một dãy số nguyên có độ dài $l$, $[a_1, a_2, \dots, a_l]$, đáp ứng các yêu cầu sau:

• $3 \le l \le 6$;
• Với mọi $i \in [1, l]$, $1 \le a_i \le 4000$;
• $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.

Little U đã cài đặt sẵn một trình chấm (checker) bằng thuật toán học trên lớp, và việc bạn cần làm là giải bài toán kiến tạo này.

Dữ liệu vào

Bài toán này gồm nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 500$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dữ liệu vào gồm một dòng duy nhất chứa một số nguyên $X$ ($1 \le X \le 10^9$), có ý nghĩa như đã nêu trong đề bài.

Dữ liệu ra

Đối với mỗi bộ dữ liệu: trước tiên in ra một dòng chứa một số nguyên $l$ ($3 \le l \le 6$), biểu thị độ dài của dãy được xây dựng. Sau đó in ra một dòng chứa $l$ số nguyên, biểu thị dãy được xây dựng.

Có thể chứng minh rằng với mọi đầu vào $X$, luôn tồn tại một cách xây dựng thỏa mãn yêu cầu. Nếu có nhiều cách xây dựng thỏa mãn yêu cầu, hãy in ra một cách bất kỳ trong số đó.

Ví dụ

Dữ liệu vào mẫu 1

2
90
10

Dữ liệu ra mẫu 1

4
5 3 2 6
3
1 1 10

Ghi chú

Đối với bộ dữ liệu đầu tiên, dãy được xây dựng là $[5, 3, 2, 6]$, biểu thị việc cần thực hiện phép nhân chuỗi ba ma trận có kích thước $5 \times 3$, $3 \times 2$ và $2 \times 6$. Xét hai chiến lược nhân:

• Trước tiên, nhân $M_1$ và $M_2$ để thu được ma trận kích thước $5 \times 2$, sau đó nhân với $M_3$, tương ứng với biểu thức $(M_1 \times M_2) \times M_3$. Tổng số phép toán lúc này là $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Trước tiên, nhân $M_2$ và $M_3$ để thu được ma trận kích thước $3 \times 6$, sau đó nhân với $M_1$, tương ứng với biểu thức $M_1 \times (M_2 \times M_3)$. Tổng số phép toán lúc này là $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Ở đây, mục tiêu là cực tiểu hóa tổng số phép toán, vì vậy $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.