#1753 Products of digits

27  1 s   128 MB  

Description

You are given an integer N. Find the smallest positive integer X such that the product of its digits (in decimal notation) is equal to N. Print the number of digits in X, or print -1 if such a number does not exist.

 

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input.

 

The one and only line of each test case contains a single integer N(0 ≤ N ≤ 109).
 

Output

Print exactly one line for each test case.

 

Sample Input

Sample Output

6
1
10
26
100
2520
864
1
2
-1
3
4
4

Source

Topcoder SRM Division 424 - Level One