SNGINT - Encode Integer

Given an integer N (0 <= N < 107), find the smallest positive integer M (M > 0) such that the product of digits of M equals N.

Input

The first line of input is T (the total number of test cases), followed by T (T < 10001) lines, each containing an integer N.

Output

For each integer N, output in a separate line the integer M, or -1 (if encoding is not possible).

Example

Input:
3
24
5
11

Output:
38
5
-1

Added by:AvmnuSng
Date:2014-02-03
Time limit:0.100s-0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Abhimanyu Singh
My Problems

hide comments
2020-06-08 14:21:40
don't think so hard answer for n=0 is 10
Finally,got it after lots of WA bruteforcing lol

Last edit: 2020-06-08 14:21:59
2019-03-14 14:35:10
You just need to think about this for a little time. The logic will come on its own. It was a nice one, costed me one WA
This is just a challenge for the people who solved this:

Try doing it in < O(N) time.

Last edit: 2019-03-15 19:50:44
2018-12-10 10:28:14
When n=0, ans is not 0... it is next smallest integer..
2018-07-15 01:22:51
Take care of the case n=0
2015-05-08 19:31:26 Vipul Srivastava
Nice one..
2014-11-27 11:57:13 Deepak Gupta
I think "another possible" should be removed, as the answer can be same, as in the given examples.
2014-11-09 15:15:59 numerix
@Deepak Gupta: According to the problem description ("product") you are right. A product needs at least two factors and m=5 is only a single number.
On the other hand: The example (n=5 -> m=5) makes it clear how to handle these cases. I got AC with that assumption.
2014-11-09 09:37:07 Deepak Gupta
Shouldn't the answer for 5 be 15??
2014-02-14 16:37:41 Mitch Schwartz
It is also my opinion that the source limit is unnecessarily small, although of course it's not a huge obstacle. I knew at time of submission that there is a quite short way to solve this, but it is also slower than what I did. So my code is just a little mutilated to pass the source limit.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.