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

hide comments
rum3r: 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
aryan12: 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
ankur314: 2018-12-10 10:28:14

When n=0, ans is not 0... it is next smallest integer..

shikher_raj55: 2018-07-15 01:22:51

Take care of the case n=0

Vipul Srivastava: 2015-05-08 19:31:26

Nice one..

Deepak Gupta: 2014-11-27 11:57:13

I think "another possible" should be removed, as the answer can be same, as in the given examples.

numerix: 2014-11-09 15:15:59

@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.

Deepak Gupta: 2014-11-09 09:37:07

Shouldn't the answer for 5 be 15??

Mitch Schwartz: 2014-02-14 16:37:41

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.


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