อย่างที่คุณทราบ คุณกำลังเข้าร่วมการแข่งขันโจทย์ปัญหาเชิงสร้างสรรค์แห่งประเทศจีน (Chinese Constructive Problem Contest - CCPC) และไม่ต้องสงสัยเลยว่ามหาวิทยาลัยผู้ออกโจทย์อย่างมหาวิทยาลัยซุนยัดเซ็น ในฐานะอาณาจักรแห่งการสร้างสรรค์ (Kingdom of Construction) ต่างก็คาดหวังเป็นอย่างยิ่งให้คุณได้ท้าทายโจทย์ปัญหาที่เกี่ยวข้อง

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 จึงคิดโจทย์ปัญหาต่อไปนี้ขึ้นมาโดยธรรมชาติ:

กำหนดจำนวนเต็ม $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$

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$