시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 200 78 72 40.000%

문제

학교에서 공부를 하고 있던 승환이는 갑자기 숫자 하나를 보고 그 숫자의 특징에 대해 생각했다. 승환이가 본 숫자는 10이다. 10은 2*5로 나타낼 수 있고 이를 조금 더 생각해서 25라는 수의 각 자릿수를 곱하면 10이 된다는 것을 알아냈다. 이를 일반적인 문제로 바꾸면 다음과 같다. 

“양의 정수 N( 1 <= N <= 1,000,000,000 )이 있을 때 모든 자릿수의 곱이 정확히 N이 되는 가장 작은 양의 정수 X를 찾아라. ”

모든 자릿수의 곱이 20인 수들을 예를 들면, 522 보다는 225가 작고 225 보다는 45가 작다.

승환이는 자신이 만든 문제를 수업 시간 전에 칠판에 써 놓았다. 그것을 본 당신은 호기심이 생겨서 그 문제를 풀어보고 싶어한다. N이 주어졌을 때 위 조건을 만족하는 가장 작은 양의 정수 X가 몇 자리 수인지 구하여라.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 <= N <= 1,000,000,000)

출력

각각의 Test case에 대해서 조건을 만족하는 가장 작은 X가 몇 자리 수인지 출력하라. 만약 그러한 X가 존재하지 않는다면 -1을 출력하라.

예제 입력

2
10
26

예제 출력

2
-1

힌트