Өздеріңіз білетіндей, сіздер Қытайдың конструктивті есептер сайысына (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 табиғи түрде келесі есепті ойлап тапты:

$1 \le X \le 10^9$ шартын қанағаттандыратын $X$ бүтін саны берілген. Сізге келесі талаптарға сай келетін, ұзындығы $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$ болатын үш матрицаны тізбектей көбейту қажеттігін білдіреді. Екі көбейту стратегиясын қарастырайық:

• Алдымен өлшемі $5 \times 2$ матрица алу үшін $M_1$ мен $M_2$ матрицаларын көбейтіп, содан кейін $M_3$ матрицасына көбейтеміз, бұл $(M_1 \times M_2) \times M_3$ өрнегіне сәйкес келеді. Бұл жағдайда жалпы амалдар саны $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$ болады;
• Алдымен өлшемі $3 \times 6$ матрица алу үшін $M_2$ мен $M_3$ матрицаларын көбейтіп, содан кейін $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$.