행복한 소수

양의 정수 $n$의 각 자리 숫자를 제곱해서 모두 더한다. 그렇게 나온 합에도 같은 계산을 다시 한다. 이 과정을 반복하다가 1이 나오면 $n$을 행복수라고 한다.

700은 행복수이다.

• $7^2 + 0^2 + 0^2 = 49$
• $4^2 + 9^2 = 97$
• $9^2 + 7^2 = 130$
• $1^2 + 3^2 + 0^2 = 10$
• $1^2 + 0^2 = 1$

2는 행복수가 아니다.

• $2^2 = 4$
• $4^2 = 16$
• $1^2 + 6^2 = 37$
• $3^2 + 7^2 = 58$
• $5^2 + 8^2 = 89$
• $8^2 + 9^2 = 145$
• $1^2 + 4^2 + 5^2 = 42$
• $4^2 + 2^2 = 20$
• $2^2 + 0^2 = 4$
• $4^2 = 16$
• 계산이 끝나지 않는다.

소수는 1과 자기 자신 말고는 약수가 없는 수이다. 2, 3, 5, 7, 11, 13, 17, 19, ...가 소수이다.

행복한 소수는 소수이면서 행복수인 수이다. 7, 13, 19, ...가 행복한 소수이다.

$n$이 주어지면 $n$보다 작거나 같은 행복한 소수를 모두 구하는 프로그램을 작성하시오.

첫째 줄에 $n$이 주어진다. ($10 \le n \le 1\,000\,000$)

$n$보다 작거나 같은 행복한 소수를 오름차순으로 한 줄에 하나씩 출력한다.