Product of digits

For a given non-negative integer number N , find the minimal natural Q such that the product of all digits of Q is equal N .

Input

The first line of input contains one positive integer number, which is the number of data sets. Each subsequent line contains one data set which consists of one non-negative integer number N (0N10⁹) .

Output

For each data set, write one line containing the corresponding natural number Q or `-1' if Q does not exist.

Sample Input

3

1

10

123456789

Sample Output

1

25

-1

题意： 给定一个整数N。。要求出一个最小的Q。。使得Q的每位的乘积等于N。。

思路：贪心。。先把N分解成质因数保存起来。。。然后拿这些质因数去组合。。由于Q要最小。所以先使得位数尽量小。再使得每个位数上的数字尽量小。。就是答案了。。因此我们在组合的时候。要尽量往大了去组合。由于只能组合成一位数。所以从9开始组合。9需要2个3，8需要3个2，6需要2和3。4需要2个2组合。。按9， 8， 6， 4的顺序组合。。最后剩下的数字一定最少。然后在组合后每个数字的个数，按从小到大输出即可。。

..然后看了别人的题解。。。才发现。。其实直接从9开始分解因子就可以了。。我还先分解成质因子了在去组合- - 2B了。没考虑清楚就直接开始写的后果。。还好这题写的还不算太长

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <limits.h>

#include <algorithm>

using namespace std;

int t, n;

int num[10];

int solve() {//质因数去组合。。

    num[9] += num[3] / 2;

    num[3] %= 2;

    num[8] += num[2] / 3;

    num[2] %= 3;

    int sb = min(num[2], num[3]);

    num[6] += sb;

    num[2] -= sb;

    num[3] -= sb;

    num[4] += num[2] / 2;

    num[2] %= 2;

}

int main() {

    scanf("%d", &t);

    while (t --) {

	scanf("%d", &n);

	memset(num, 0, sizeof(num));

	if (n == 0 || n == 1) {//0和1单独出来考虑。

	    printf("%d\n", n);

	    continue;

	}

	for (int i = 2; i <= 7; i ++) {//分解质因数枚举到7就可以了。因为一个位数上的数字必须是一位数。

	    while (n % i == 0 && n != i) {

		num[i] ++;

		n /= i;

	    }

	}

	if (n > 9)

	    printf("-1\n");

	else {

	    num[n] ++;

	    solve();

	    for (int i = 2; i <= 9; i ++) {//按从小到大输出。

		while (num[i]) {

		    printf("%d", i);

		    num[i] --;

		}

	    }

	    printf("\n");

	}

    }

    return 0;

}