시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB126837264.865%

문제

The Goldbach Conjecture states that any even number greater than 3 can be expressed as the sum of two primes (primes are numbers that have exactly two factors: themselves and 1). It has never been proven for all even numbers, but it has been demonstrated to be true for all of the numbers that we’ll use for this problem.

Consider any even integer x>3. There may be many pairs of primes which sum to x. Take the pair with the largest difference. That difference must be even, and less than x. So, repeat the trick. How many steps does it take until you reach an even number less than 3 (2 or 0)?

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.

Each test case will consist of a single line with a single integer x (0 ≤ x ≤ 106, x is even).

출력

Output a single integer, which is the count of Repeating Goldbach steps until the number is less than 3.

예제 입력 1

20

예제 출력 1

3

예제 입력 2

30

예제 출력 2

4

예제 입력 3

40

예제 출력 3

5

예제 입력 4

50

예제 출력 4

6

예제 입력 5

60

예제 출력 5

7

예제 입력 6

70

예제 출력 6

8