불량 난수

Bessie는 무작위처럼 보이는 수를 만들고 싶어 합니다. Bessie는 중앙 제곱법(middle-square method) 이라는 오래된 방법을 찾았는데, 규칙은 다음과 같습니다.

• 네 자리 수 $N$에서 시작합니다($1 \le N \le 9999$이며, 네 자리보다 짧은 수는 앞을 0으로 채워 네 자리로 봅니다).
• 가운데 두 자리, 즉 백의 자리와 십의 자리를 두 자리 수로 읽습니다.
• 그 두 자리 수를 제곱합니다. 이 제곱값이 다음 "난수"가 되며, 동시에 새로운 시작 수가 됩니다.

예를 들어 7339에서 시작하면 다음과 같습니다.

  수  가운데  제곱
7339    33     1089
1089     8       64
  64     6       36
  36     3        9
   9     0        0
   0     0        0

비둘기집 원리에 따라 이 값들은 최대 10000단계 안에 반드시 반복됩니다. 위 예에서는 난수 여섯 개가 생성된 뒤부터 값이 반복됩니다(수열이 0에 도달하면 이후 값은 모두 0입니다).

더 복잡하게 반복되는 경우도 있습니다. 2245에서 시작하면 값이 576과 3249 사이를 오갑니다.

  수  가운데  제곱
2245   24      576
 576   57     3249
3249   24      576

시작 수 $N$에서 출발하여, 수열에 이미 나온 적이 있는 값이 처음으로 다시 생성될 때까지(그 반복되는 값 자체도 포함하여) 생성된 난수의 개수를 세십시오. 시작 수도 "이미 나온 값"으로 봅니다. 7339의 경우 이 개수는 6이고, 2245의 경우 3입니다.

정수 $N$ 하나가 한 줄에 주어집니다($1 \le N \le 9999$).

중앙 제곱법을 시작 수 $N$부터 진행할 때, 이미 나온 적이 있는 값(시작 수 포함)이 처음으로 다시 생성될 때까지 생성된 난수의 개수를 정수 한 줄로 출력합니다. 반복되는 값 자체도 개수에 포함합니다.