User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

80.0% (16/20)

Description

魔理沙為了學習魔法來到了魔法都市,眾所皆知施放魔法需要詠唱魔法文字

施放的方法如下:
一個魔法有數種詠唱方式,而第 $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$

Input Format

每筆輸入包含一個正整數 $N$,其中 $N \leq 10^ 9$

Output Format

對於每筆輸入請輸出對應的詠唱順序

Sample Input 1

1

Sample Output 1

1

Sample Input 2

420

Sample Output 2

2567

Sample Input 3

81

Sample Output 3

99

Hints

本題使用special judge

Problem Source

Subtasks

No. Testdata Range Score
1 0~11 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 100 65536 65536 1
1 100 65536 65536 1
2 100 65536 65536 1
3 100 65536 65536 1
4 100 65536 65536 1
5 100 65536 65536 1
6 100 65536 65536 1
7 100 65536 65536 1
8 100 65536 65536 1
9 100 65536 65536 1
10 100 65536 65536 1
11 100 65536 65536 1