Số nguyên tố họ hàng là một cặp số nguyên tố lệch nhau 4 đơn vị.

Ví dụ

các cặp số ~(3,7), (7,11), (13,17)~ là các cặp số nguyên tố họ hàng.

Yêu cầu

Cho trước một số tự nhiên ~N~. hãy xem có bao nhiêu cặp số nguyên tố họ hàng không lớn hơn ~N~.

Dữ liệu

• Một dòng ghi số tự nhiên ~N~ ~(N \leq 10^6)~.

Kết quả

• Một dòng ghi số lượng số nguyên tố họ hàng không lớn hơn ~N~.

Ví dụ

Cho một số nguyên dương ~n~, đếm số ước của nó.

Input format

• Dòng đầu chứa số nguyên ~t~ là số bộ thử.
• ~t~ dòng sau mỗi dòng chứa một số nguyên ~n~.

Output format

• Gồm ~t~ dòng in ra kết quả mỗi bộ thử.

Constraints

• ~0<t\leq 10^5~</li>
• ~0<n\leq 10^7~</li>

Example

Sample Input

3
4
12
20

Sample Output

3
6
6

Cho số nguyên dương ~N~ dạng 32bit.

Yêu cầu

Hãy tìm khoảng cách giữa ~N~ và số nguyên tố nhỏ nhất lớn hơn $N$.

Input

1 dòng duy nhất ghi số nguyên ~N~.

Output

• Dòng đầu tiên ghi số nguyên tố nhỏ nhất lớn hơn ~N~.
• Dòng thứ hai ghi khoảng cách giữa chúng.

Ví dụ

INPUT

9

OUTPUT

11
2