Eins og þú veist tekur þú þátt í Kínversku keppninni í smíðaverkefnum (Chinese Constructive Problem Contest, CCPC), og án nokkurs vafa er háskólinn sem semur dæmin, Sun Yat-sen-háskólinn, sem Konungsríki smíðanna, mjög ákafur í að sjá þig glíma við nokkur tengd verkefni.

Litli U er nemandi í Konungsríki smíðanna. Í reikniritsáfanga lærði Litli U um MCOP (Matrix Chain Ordering Problem — röðunarvandamál fylkjakeðjumargföldunar). Hér er kynning á MCOP:

Gefin er runa jákvæðra heiltalna af lengd $n \ge 3$, $[w_1, w_2, \dots, w_n]$, sem inntak í reikniritið. Eftirfarandi formúla margfaldar saman $n - 1$ fylki til að fá að lokum nýtt fylki:

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

þar sem $M_i$ er fylki af stærð $w_i \times w_{i+1}$. Fylkjamargföldun uppfyllir tengireglu, þannig að breytt röð margföldunar skilar sama lokafylki $M$, en fjöldi aðgerða getur verið mismunandi. Markmið verkefnisins er að finna besta margföldunarháttinn af $(n - 2)!$ mögulegum leiðum, þannig að heildarfjöldi aðgerða sem þarf til fylkjamargföldunarinnar sé lágmarkaður. Hér er gert ráð fyrir að margföldun fylkja af stærðum $p \times q$ og $q \times r$ skili fylki af stærð $p \times r$ og krefjist $pqr$ aðgerða. Lágmarks heildarfjöldi aðgerða sem þarf til að reikna $M$ með besta margföldunarhætti er táknaður með $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Litli U hefur lært í tíma hvernig leysa má þetta verkefni með nægilega góðri tímaflækju, en sem nemandi í Konungsríki smíðanna datt Litla U eðlilega eftirfarandi verkefni í hug:

Gefin er heiltala $X$ sem uppfyllir $1 \le X \le 10^9$. Þú þarft að smíða heiltalnarunu af lengd $l$, $[a_1, a_2, \dots, a_l]$, sem uppfyllir eftirfarandi skilyrði:

• $3 \le l \le 6$;
• Fyrir öll $i \in [1, l]$ gildir $1 \le a_i \le 4000$;
• $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.

Litli U hefur þegar útfært prófara (checker) með reikniritinu sem hann lærði í tíma, og það sem þú þarft að gera er að leysa þetta smíðaverkefni.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 500$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik samanstendur inntakið af einni línu með heiltölu $X$ ($1 \le X \le 10^9$), en merking hennar hefur verið útskýrð í dæminu.

Úttak

Fyrir hvert prófunartilvik: prentið fyrst línu með heiltölu $l$ ($3 \le l \le 6$), sem táknar lengd smíðuðu rununnar. Prentið síðan línu með $l$ heiltölum, sem tákna smíðuðu rununa.

Sanna má að fyrir sérhvert inntak $X$ er alltaf til smíð sem uppfyllir skilyrðin. Ef fleiri en ein smíð uppfyllir skilyrðin skal prenta hvaða eina sem er þeirra.

Dæmi

Sýnidæmi inntaks 1

2
90
10

Sýnidæmi úttaks 1

4
5 3 2 6
3
1 1 10

Athugasemd

Fyrir fyrsta prófunartilvikið er smíðaða runan $[5, 3, 2, 6]$, sem táknar að framkvæma þurfi keðjumargföldun þriggja fylkja af stærðum $5 \times 3$, $3 \times 2$ og $2 \times 6$. Skoðum tvær margföldunarleiðir:

• Margfalda fyrst $M_1$ og $M_2$ til að fá fylki af stærð $5 \times 2$, og margfalda síðan við $M_3$, sem samsvarar segðinni $(M_1 \times M_2) \times M_3$. Heildarfjöldi aðgerða er þá $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Margfalda fyrst $M_2$ og $M_3$ til að fá fylki af stærð $3 \times 6$, og margfalda síðan við $M_1$, sem samsvarar segðinni $M_1 \times (M_2 \times M_3)$. Heildarfjöldi aðgerða er þá $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Hér er markmiðið að lágmarka heildarfjölda aðgerða, þannig að $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.