Sau tiết học tiềm hiểu về số nguyên tố, giờ ra chơi Việt và Nam là hai người bạn cùng ngồi chung một bàn đã cùng nhau suy nghĩ để giải một bài toán cô giáo vừa giao như sau: Tìm tất cả các cách để phân tích số nguyên dương ~N~ thành tổng của hai số nguyên tố. Với số ~N~ nhỏ, Việt và Nam đã thực hiện tốt, tuy nhiên khi thực hiện bài toán với số ~N~ lớn thì chưa thực hiện được. Em hãy giúp hai bạn giải quyết vấn đề này nhé.

Yêu cầu

Tìm số ~K~ là số cách phân tích số ~N~ thành tổng hai số nguyên tố.

Dữ liệu đầu vào

Gồm một số nguyên dương ~N~ ~(N < 3 \times 10^7)~.

Dữ liệu đầu ra

Gồm một số nguyên ~K~.

Ví dụ

Ví dụ 1

INPUT

6

OUTPUT

1

Ví dụ 2

INPUT

10

OUTPUT

2

Ví dụ 3

INPUT

17

OUTPUT

0