魔理沙為了學習魔法來到了魔法都市,眾所皆知施放魔法需要詠唱魔法文字
施放的方法如下:
一個魔法有數種詠唱方式,而第 $i$ 種詠唱包含數個魔法文字 $K_{ij}$
完成魔法 $N$ 需要滿足 $\prod_{j=1}^ {D_i}K_{ij}=N$,其中 $D_i$ 為第 $i$ 種詠唱的文字數量
例如魔法 $42$,則可以有 $3 \cdot 14 = 2 \cdot 3 \cdot 7 = 2 \cdot 21 = 42$ 這些詠唱方式
因此最快速的詠唱方式就是直接詠唱 $42$
而每種魔法文字有對應的能量,越大的文字能量越大
魔法使們需要從能量最小的文字開始依序詠唱,否則魔法會失敗
但身為見習魔法使的魔理沙只能詠唱其中最弱的 $9$ 種魔法文字($1$ 到 $9$)
為了能快速的使出某魔法 $N$,魔理沙請你幫忙她找出最快的詠唱方式
若魔理沙目前還無法詠唱該魔法,請輸出$-1$
每筆輸入包含一個正整數 $N$,其中 $N \leq 10^ 9$
對於每筆輸入請輸出對應的詠唱順序
本題使用special judge
No. | Testdata Range | Score |
---|---|---|
1 | 0~11 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 100 | 65536 | 65536 | |
1 | 100 | 65536 | 65536 | |
2 | 100 | 65536 | 65536 | |
3 | 100 | 65536 | 65536 | |
4 | 100 | 65536 | 65536 | |
5 | 100 | 65536 | 65536 | |
6 | 100 | 65536 | 65536 | |
7 | 100 | 65536 | 65536 | |
8 | 100 | 65536 | 65536 | |
9 | 100 | 65536 | 65536 | |
10 | 100 | 65536 | 65536 | |
11 | 100 | 65536 | 65536 |