You have an array of Q integers.
Dae Koon sees your array of integers and wonders, for each integer in the array Ai, how many integers from 1 to Ai (inclusive) are not divisible by any integer from 2 to 10 (inclusive)?
The first line of input contains a single integer Q.
The next line contains Q integers, the ith integer is the value of Ai.
Output Q lines, with one integer on each line.
The integer on the ith line should be the answer to Dae Koon's question for Ai.
Subtask 1 (100%): 1 ≤ Q ≤ 106. 2 ≤ Ai ≤ 1018.
Subtask 2 (0%): Sample Testcases