Though Naval is always serious for his exams , but sometimes he cannot keep himself focused in Maths. In today's Maths exam, Naval was asked to find total count of prime numbers which are less than or equal to the given number n , but because of hurry he misunderstood prime numbers to be odd numbers and calculated total count of odd numbers which are less than or equal to the given number n.
After the exam , Naval's friend Kailash dragged his attention towards the error Naval made. Now Naval is disappointed because of the error and asks Kailash to tell him the absolute difference between his answer and correct answer.

Input

First line of input contains t (no. of test cases to follow) . Next t lines contains a single integer n (the number given).

Output

Print t lines each containing the absolute differnce in answers for given number n.

Constraints

1<= t <= 100
1<= n <= 10^6

Example

Input:
3
5
12
20

Output:
0
1
2

Explanation

for 3rd test case , given number n = 20.
Prime numbers less than or equal to n are 2,3,5,7,11,13,17,19 (total 8).
Odd numbers less than or equal to n are 1,3,5,7,9,11,13,15,17,19 (total 10).
so the answers is absolute difference between them i.e. 2.