시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1148 | 397 | 349 | 35.217% |
학교에서 공부를 하고 있던 승환이는 갑자기 숫자 하나를 보고 그 숫자의 특징에 대해 생각했다. 승환이가 본 숫자는 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