양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.

700은 상근수이다.

• 7² + 0² + 0² = 49
• 4² + 9² = 97
• 9² + 7² = 130
• 1² + 3² + 0² = 10
• 1² + 0² = 1

2는 상근수가 아니다.

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

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

소수상근수는 소수이면서 상근수인 숫자이다. 7, 13, 19, ... 는 소수 상근수이다.

n이 주어졌을 때, n보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 n (10 ≤ n ≤ 1000000)이 주어진다.

출력 형식

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

예제 입력

20

예제 출력

7
13
19