Repeating Goldbachs

Time limit2sMemory limit512 MB

Summary

Apply the largest-difference Goldbach step to an even x under 1,000,000 until it drops below 3, and count the steps.

Level: Medium7 of 10
Topics: Number theory, Simulation, Math, Brute force
Solved: No attempts yet

Problem

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 will 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)?

Input

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 \le x \le 10^6$ , $x$ is even).

Output

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

Examples5

Example 1
Input
```
20
```
Expected output
```
3
```
Example 2
Input
```
30
```
Expected output
```
4
```
Example 3
Input
```
40
```
Expected output
```
5
```
Example 4
Input
```
50
```
Expected output
```
6
```
Example 5
Input
```
60
```
Expected output
```
7
```