Number Play

Interview

Time limit1sMemory limit128 MB

Summary

For each N, greedily factor it into digits 9 down to 2 to find the minimum digit count of a number whose digits multiply to N, or report -1 if impossible.

Level: Medium4 of 10
Topics: Greedy, Math, Number theory
Solved: No attempts yet

Problem

Given a positive integer N, consider the smallest positive integer X whose decimal digits multiply to exactly N. For instance, when N = 20, both 225 and 522 have digit product 20, but the smaller number 45 also satisfies the condition.

For each test case, determine whether such an X exists. If it exists, output the number of digits in the smallest such X. If it does not exist, output -1.

Input

The first line contains the number of test cases T. Each test case consists of one line containing a positive integer N. (1 <= N <= 1,000,000,000)

Output

For each test case, output one line containing the number of digits in the smallest positive integer X that satisfies the condition. If no such X exists, output -1.

Examples1

Example 1
Input
```
2
10
26
```
Expected output
```
2
-1
```