Number Play

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.

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)

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.