indivisibility

Problem Description

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)?

Input

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

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.

Limits

Subtask 1 (100%): 1 ≤ Q ≤ 106. 2 ≤ Ai ≤ 1018.

Subtask 2 (0%): Sample Testcases

Sample Testcase 1

Input

1
12

Output

2

Submitting to 'indivisibility'


You're not logged in! Click here to login


Submitting to 'indivisibility'


You're not logged in! Click here to login


Submitting .cpp to 'indivisibility'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 18
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0