시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 96 87 82.857%

## 문제

Bessie is trying to generate random numbers. She stumbled upon an old reference to the 'middle square' method for making numbers that appear to be random. It works like this:

• Pick a starting four digit number (1 <= N <= 9999)
• Extract its middle two digits (the hundreds and tens digit) as a number
• Compute the square of those two digits
• That square is the 'random number' and becomes the new starting number

Here's a sample:

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

The 'pigeon hole principle' tells us that the random numbers surely must repeat after no more than 10,000 of them -- and the sequence above repeats after just six numbers (the next number and all subsequent numbers are 0).

Note that some sequences repeat in a more complex way; this one alternates back and forth between 576 and 3249:

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

Your job is to tell Bessie the count of 'random numbers' that can be generated from a starting number before the sequence repeats a previously seen number. In the first case above, the answer is '6'. In the 'alternating' case, the answer is '3'.

## 입력

• Line 1: A single integer: N

## 출력

• Line 1: A single integer that is the count of iterations through the middle square random number generator before a previous value is repeated

## 예제 입력 1

7339


## 예제 출력 1

6