Cho số nguyên dương ~x~, với giá trị ~x~ ta xây dựng hàm ~f(x)~ là số lượng lớn nhất các số nguyên tố mà tổng của chúng có giá trị bằng ~x~ và đồng thời thỏa mãn ràng buộc: Mỗi số nguyên tố được sử dụng một lần, chỉ duy nhất một số nguyên tố nào đó có thể được sử dụng 2 lần (nếu thấy cần thiết).

Ví dụ:

• Với ~x = 5~ ta có ~f(x) = 2~ vì ~5 = 2 + 3~, mỗi số nguyên tố được sử dụng một lần.
• Với ~x = 7~ ta có ~f(x) = 3~ vì ~7 = 2 + 3 + 2~, số nguyên tố 3 được sử dụng một lần, số nguyên tố 2 được sử dụng 2 lần.
• Ta quy ước ~f(1) = 1~.

Yêu cầu:

Với mỗi số nguyên dương ~x~ cho trước, hãy tìm giá trị của hàm ~f(x)~.

Dữ liệu vào:

Cho trong file văn bản COUNTPRIME.INP, có cấu trúc như sau:

• Dữ liệu được ghi trên nhiều dòng, mỗi dòng ghi một số nguyên dương ~x~ ~(1 \leq x \leq 10^4)~.
• File dữ liệu vào có không quá ~10^4~ dòng.

Kết quả:

Ghi ra file văn bản COUNTPRIME.OUT, theo cấu trúc như sau:

• Gồm nhiều dòng: Mỗi dòng ghi giá trị của hàm ~f(x)~ tìm được tương ứng với một dòng của file dữ liệu vào.

Ví dụ:

Test 01

Input: COUNTPRIME.INP

2
10
5
17

Output: COUNTPRIME.OUT

1
3
2
4

Test 02

Input: COUNTPRIME.INP

3
7
14

Output: COUNTPRIME.OUT

1
3
4