Sau tiết học tìm hiểu về số nguyên tố, giờ ra chơi Việt và Nam là 2 người bạn cùng ngồi chung 1 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 một số nguyên dương N thành tổng 2 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 N lớn thì chưa thực hiện được. Em hãy giúp 2 bạn giải quyết bài toán trên.

Yêu cầu: Tìm K là số cách phân tích số N thành tổng 2 số nguyên tố.

Input:

Cho trong tệp văn bản NGUYENTO.INP có cấu trúc:

• Dòng 1: Ghi số nguyên dương N ~(N < 3.10^7)~

Output:

Ghi ra tệp văn bản NGUYENTO.OUT với cấu trúc:

• Dòng 1: Ghi số K.

Example:

Input:

10

Output:

2

Giải thích: Có 2 cách phân tích số 10 thành tích 2 số nguyên tố là: 3+7 và 5+5