Cho một số nguyên dương ~n~. Bạn hãy đếm số cách phân tích số ~n~ thành tổng hai số nguyên tố khác nhau ~u,v\ (u< v)~.

Input

• Số nguyên dương ~n\ (2≤n≤3×10^5)~.

Output

• Dòng đầu ghi một số nguyên ~k~ là số cách phân tích thỏa mãn điều kiện đề bài. Nếu không có cách phân tích ghi số ~0~.
• Trường hợp ~k>0, k~ dòng tiếp theo, dòng thứ ~i~ ghi hai số ~u_i,v_i\ (u_i< v_i)~ là cách phân tích thứ ~i~ theo yêu cầu: ~u_1< u_2<…< u_k~.

Sample

Input #1

82

Output #1

4
3 79
11 71
23 59
29 53

Input #2

11

Output #2

0

Hint

• Số ~82~ có ~4~ cách phân tích ~82=3+79=11+71=23+59=29+53~. Cách phân tích ~82=41+41~ không được tính vì ~u=v~.
• Số ~11~ không phân tích được.

Problem source: Chuyên Sơn La Online Judge