كما تعلم، أنت تشارك في المسابقة الصينية للمسائل البنائية (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$.