Bad Random Numbers

프로그램 명: usa_badrand

제한시간: 1 초

[문제요약] 네자리수 이하의 자연수를 입력받아, 세번째 자릿수와 두번째 자릿수를 합쳐서 두 자리수 이하의 수를 만드는 과정 k를 수행한다. 같은 수가 나오지 않을 때까지 과정 k를 수행한 횟수를 출력한다.

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

입출력 예

입력

7339


출력

6

출처:usaco 2010 DEC bronze
요약: pl0892029

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]