가운데 제곱
면접 대비시간 제한1초메모리 제한1024 MB
네 자리 수에서 가운데 두 자리를 꺼내 제곱하는 과정을 반복하고, 같은 수가 처음 다시 나올 때까지의 횟수를 구합니다.
문제
Bessie의 딸 Cassie는 송아지 학교에서 새로운 수학 문제를 가지고 왔다. "계산을 다 할 수 있을지 모르겠어요." 그녀가 투덜거렸다.
"무슨 계산을 하고 있는 거니?" 걱정스러운 어머니가 물었다.
"우리는 10,000보다 작은 양의 정수 N을 받아요." Cassie가 대답했다. "12처럼 두 자리 수라도 네 자리 수로 취급해요. 두 번째와 세 번째 자릿수를 뽑아서 새로운 수를 만들고, 그 수를 제곱하면 또 네 자리 수가 나와요. 이미 본 수가 나올 때까지 이 과정을 반복해요."
불쌍한 Cassie의 숙제를 도와주자. 다음은 4444에서 시작하는 예시이다:
N 2nd&3rd Squared
4444 ... 0044 ... 1936
1936 ... 0093 ... 8649
8649 ... 0064 ... 4096
4096 ... 0009 ... 0081
0081 ... 0008 ... 0064
0064 ... 0006 ... 0036
0036 ... 0003 ... 0009
0009 ... 0000 ... 0000
0000 ... 0000 ... 0000
이 예시는 완료하는 데 9번의 반복이 필요하다. 0000은 가운데 제곱도 0000이므로 반복이 생긴다.
입력
첫째 줄에 정수 N이 주어진다.
출력
어떤 수가 중복되기 전까지 반복한 횟수를 출력한다.