숫자 놀이

양의 정수 N이 주어진다. 각 자릿수의 곱이 정확히 N이 되는 양의 정수 X 중에서 가장 작은 X를 생각하자. 예를 들어 N = 20일 때 225와 522도 자릿수의 곱이 20이지만, 더 작은 45도 조건을 만족한다.

각 테스트 케이스마다 이런 X가 존재하는지 판단하고, 존재한다면 그 가장 작은 X의 자릿수를 출력해야 한다. X가 존재하지 않으면 -1을 출력한다.

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스마다 한 줄에 양의 정수 N이 주어진다. (1 <= N <= 1,000,000,000)

각 테스트 케이스마다 조건을 만족하는 가장 작은 양의 정수 X의 자릿수를 한 줄에 출력한다. 그런 X가 없으면 -1을 출력한다.