BẠN NGUYÊN TỐ

Số nguyên tố là số nguyên dương chỉ có đúng 2 ước số là 1 và chính nó. Hai số được gọi là bạn nguyên tố của n khi cả hai đều là nguyên tố và có tổng giá trị bằng n.

Yêu cầu

• Hãy đếm xem có bao nhiêu cặp bạn nguyên tố của n.

Dữ liệu vào

• Được nhập từ bàn phím một số nguyên n (1 ≤ n ≤ 10^6).

Kết quả

• Ghi ra màn hình một số nguyên là số cặp bạn nguyên tố.

Ràng buộc

• Có 70% số test tương ứng với 70% số điểm có 1 ≤ n ≤ 10^4.
• Có 30% số test tương ứng với 30% số điểm có 10^4 < n ≤ 10^6.

Ví dụ