행복한 수(happy number)는 각 자리수의 제곱의 합을 구해 나가는 과정을 연속적으로 적용하였을 때, 1까지 도달하는 수를 말한다. 좀 더 정확히 정의해 보자면, 주어진 양의 정수 n에 대하여 다음과 같은 수열을 정의할 수 있다:
n0, n1, n2, ...
여기에서, n0=n이고, ni+1은 ni의 모든 자리수의 제곱의 합이다. 만약에 이 수열에서 ni=1인 경우가 있으면 n은 행복한 수이다.
n이 행복한 수이면 위의 수열의 모든 ni는 행복한 수이다.
예를 들어, 7은 행복한 수인데 그 이유는 다음과 같은 수열이 만들어지기 때문이다
7, 49, 97, 130, 10, 1
7^2 = 49
4^2 + 9^2 = 97
9^2 + 7^2 = 130
1^2 + 3^2 + 0^2 = 10
1^2 + 0^2 = 1

하나의 양의 정수가 주어졌을 때, 주어진 정수보다 작거나 같은 정수 중에서 최대의 행복한 수를 구하는 프로그램을 작성하시오.

하나의 정수 n이 입력된다. (1≤n≤1,000)

입력된 양의 정수보다 작거나 같은 정수 중에서 가장 큰 행복한 수를 출력한다.