무작위 숫자

도서관에서 미지는 무작위 숫자를 만드는 '가운데 제곱' 방법에 대한 오래된 참고 자료를 찾았습니다.

이 방법의 원리는 다음과 같습니다:

• 시작할 네 자리 숫자를 선택합니다 (1 <= N <= 9999)
• 그 숫자의 가운데 두 자리 수 (백의 자리와 십의 자리)를 숫자로 추출합니다
• 그 두자리의 제곱근을 계산합니다
• 그 제곱은 '무작위 숫자'가 되고, 새로운 시작 숫자가 됩니다

다음은 예시입니다:

                Num  Middle  Square
               7339    33     1089
               1089     8       64
                 64     6       36
                 36     3        9
                  9     0        0
                  0     0        0

'비둘기 집 원리'에 따르면, 무작위 숫자들은 반드시 10,000개 이하로 반복되어야 하며, 위의 수열은 단 6개의 숫자(다음 숫자와 그 이후의 모든 숫자는 0)가 반복됩니다.

일부 시퀀스는 더 복잡한 방식으로 반복되는데, 이 시퀀스는 576과 3249 사이를 번갈아 가며 반복되는 것을 주의하십시오.

                Num  Middle  Square
                2245   24      576
                 576   57     3249
                3249   24      576

당신의 목표는 시퀀스가 이전에 본 숫자를 반복하기 전에, 시작 숫자로부터 생성될 수 있는 '무작위 숫자'의 개수를 미지에게 알려주는 것입니다. 위의 첫 번째 경우에서 답은 '6'입니다. '교대' 경우에는 '3'입니다.

• 첫 번째 줄: 단일 정수: N

• 첫 번째 줄: 이전 값이 반복되기 전에 가운데 제곱 방법을 통한 무작위 숫자 생성을 통해 반복되는 회수를 나타내는 단일 정수