랜덤 숫자 만들기

존 폰 노이만(John von Neumann)은 1946년에 유사난수(pseudo-random number) 수열을 만드는 방법을 제안했다. 이 방법은 중간제곱법(middle-square method)이라고 불리며, 다음과 같이 동작한다.

먼저 초기값 $a_0$을 정한다. $a_0$은 십진법으로 나타냈을 때 자릿수가 $n$을 넘지 않아야 한다. 다음으로 $a_0$을 제곱한 뒤, 그 결과의 자릿수가 $2n$이 되도록 앞에 $0$을 채운다. 이렇게 만든 $2n$자리 수의 가운데 $n$자리를 $a_1$로 삼는다. 같은 규칙을 반복하면 모든 $i > 0$에 대해 $a_i$를 구할 수 있다. 이 문제에서는 $n = 4$로 고정한다.

예 1: $a_0 = 5555$이면 $a_0^2 = 30858025$이므로, 가운데 네 자리를 취해 $a_1 = 8580$이 된다.

예 2: $a_0 = 1111$이면 $a_0^2 = 01234321$(앞에 $0$을 채워 여덟 자리로 만든 값)이므로, $a_1 = 2343$이 된다.

사실 이 방법은 좋은 난수 생성기가 아니다. 수열은 언젠가 이전에 나왔던 값을 다시 만들어 내며 순환에 빠지기 때문이다.

$a_0$이 주어졌을 때, 이 수열이 처음으로 값을 반복하기 전까지 만들어 내는 서로 다른 수의 개수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄에 정수 $a_0$ 하나로 주어진다 ($0 < a_0 < 10000$). $a_0$이 네 자리가 아니면 앞에 $0$을 채워 네 자리로 표기한다. 입력의 마지막 줄에는 $0$ 하나가 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 수열에 나타나는 서로 다른 $a_i$의 개수를 한 줄에 출력한다. $a_0$도 세는 값에 포함한다.