כידוע לכם, אתם משתתפים בתחרות הסינית לבעיות קונסטרוקטיביות (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$.