A * B

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Your task is to find the minimal positive integer number Q so that the product of digits of Q is exactly equal to N.

Input

The first line of input contains T, number of test cases.
The following T lines each contain a single integer number N (0<=N<=2^31-1).

Output

For each test case, your program should first print to the output "Case #i:"(i is the case number) in one line, and then the number Q in the second line. If such a number does not exist print -1.

Sample Input

1

10

Sample Output

Case #1:
25

Hint

 

Source

HDU sdlzx