Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (~1690-1764~) nêu ra vào năm ~1742~ trong một lá thư gửi tới nhà toán học Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung. Giả thuyết phỏng đoán rằng:

Mỗi số tự nhiên chẵn lớn hơn ~2~ có thể biểu diễn bằng tổng của hai số nguyên tố.

Giá thuyết chỉ ra là đúng tới ~4 * 10^{18}~, nhưng hiện nay vẫn chưa được chứng minh hoàn toàn.

Bằng kiến thức tin học em hãy thực hiện thử thách sau: Cho trước số ~x~ là số tự nhiên chẵn lớn hơn ~2~.

Yêu cầu

Hãy cho biết có bao nhiêu cách phân tích số ~x~ thành tổng của ~2~ số nguyên tố

Lưu ý: Nếu phân tích được ~x = a + b~ hay ~x = b + a~ (trong đó ~a~ và ~b~ là các số nguyên tố) thì cũng chỉ được tính là một cách phân tích

Input

• Một số ~x~ là số tự nhiên chẵn lớn hơn ~2~

Output

• Số ~m~ theo yêu cầu

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~x\le 10^3~.
• Subtask ~2~ (~30\%~ số điểm): ~10^3\le x \le 10^4~.
• Subtask ~3~ (~20\%~ số điểm): ~10^4 \le x \le 10^6~

Ví dụ

Input

10

Output

2

Giải thích ví dụ

• ~10 = 3 + 7 = 5 + 5~