Cho số nguyên ~n~ hãy cho biết có bao nhiêu số nguyên tố không lớn hơn ~n~ có thể viết được dưới dạng ~x^2+y^4~ với ~x, y~ là hai số nguyên.

Dữ liệu:

• Dòng thứ nhất chứa số nguyên ~T(1 \le T \le 10000)~ là số test;

• ~T~ dòng tiếp theo mỗi dòng chứa một số nguyên ~n(1 \le n \le 10^7)~.

  Kết quả:

• Ghi ra ~T~ dòng, mỗi dòng gồm ~1~ số nguyên là đáp án bài toán.

  Ví dụ:

Sample Input

3
1
2
10

Sample Output

0
1
2

Ràng buộc:

• Có ~50\%~ số test có ~t \le 10, n \le 1000~;
• ~50\%~ số test còn lại không giới hạn gì thêm.