숫자 놀이
면접 대비시간 제한1초메모리 제한128 MB
각 N에 대해 9부터 2까지 탐욕적으로 나누어 숫자들의 곱이 N이 되는 최소 자릿수를 구하고, 불가능하면 -1을 출력합니다.
문제
양의 정수 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을 출력한다.