Kakezan

시간 제한3초메모리 제한512 MB

요약

음이 아닌 정수가 주어질 때, 십진수 표기를 임의의 위치에서 잘라 두 부분의 곱 중 최댓값으로 바꾸는 과정을 한 자리 수가 될 때까지 반복하고 걸린 횟수를 구하며, 영원히 끝나지 않으면 -1을 출력한다.

문제

타로는 곱셈을 막 배운 초등학생이다. 어쩐지 곱셈이 마음에 들어서, 숫자를 보면 곱셈을 하고 싶어진다. 그런 그가 요즘 즐겨 하는 작업은 0 이상의 정수에 다음과 같은 처리를 반복해서 적용하는 것이다.

1단계. 어떤 0 이상의 정수 $n$ 이 10진수로 한 자리라면 처리를 끝낸다. 그렇지 않으면 2단계로 간다.
2단계. 10 이상의 정수 $n$ 을 10진수로 나타냈을 때 어느 자리 사이든 잘라 두 수로 나눌 수 있다(예: $2012 \to 20, 12$ ). 가능한 모든 자르는 방법에 대해 얻은 두 수를 곱해 가장 큰 값을 다음 $n$ 으로 삼고 1단계로 돌아간다. 자세한 내용은 아래 "2단계에 대한 보충"을 참고한다.

타로는 이 처리를 마음에 들어 하지만, 큰 수에서는 2단계를 몇 번 반복해야 하는지 예상할 수 없고 어쩌면 무한히 반복해야 할지도 모른다고 생각한다. 그래서 타로의 형인 대학생인 당신에게 0 이상의 정수 $n$ 에 대해 이 2단계를 몇 번 해야 하는지 물어보았다.

당신이 할 일은 $Q$ 개의 0 이상의 정수 N1..NQ가 주어질 때, 각 정수에서 처리가 끝날 때까지 2단계가 몇 번 수행되는지 구하는 것이다. 만약 무한히 반복해야 한다면 -1을 출력한다.

자른 결과의 맨 앞에 0이 붙는 경우도 고려해야 한다. 예를 들어 $n=1024$ 일 때, $1*024$ , $10*24$ , $102*4$ 를 각각 계산하면 24, 240, 408이 되므로 408이 선택되고, 이것이 다음 $n$ 이 된다.

Q
N1
N2
...
NQ

Q개의 정수를 줄바꿈으로 구분해 출력한다.

R1
R2
..
RQ