## #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 Output

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

## Source

Topcoder SRM Division 424 - Level One