Find The Minimum Number Q

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

对于一个给定的非负整数N,找到一个最小的自然数Q,使得Q的每一位数字的乘积等于N

Input

第一行包含一个整数T,表示测试数据的个数 下面是T行非负整数,即给定的N (0<=N<=10^8)

Output

对于每个给定的N,输出对应的自然数Q,如果Q不存在,那么就输出‘-1’

Sample Input

3 
1 
10 
12345678

Sample Output

1 
25 
-1

Hint

如果N=0,输出-1

Source

NJUST_lmm333

提交代码