primes-1

We call a positive number of the form $a b^2 c^3$, where $a < b < c$ are prime numbers, a $123$ number. How many $123$ numbers are there in the interval $[1, N]$ ($Y$)?

Input specification

The first line contains $T$, the number of test cases. Then $T$ lines follow with the numbers $N_k ~~ (k=1\ldots T)$.

Output specification

$T$ lines with the requested numbers $Y_k~~(k=1\ldots T)$.

Constraints

$1\le T \le 100$
$1\le N_k \le 1\_000\_000\_000\_000\_000$

Sample input 1

1. 8
2. 10000
3. 100000
4. 1000000
5. 10000000
6. 100000000
7. 1000000000
8. 10000000000
9. 100000000000

Sample output 1

1. 2
2. 9
3. 33
4. 105
5. 316
6. 900
7. 2482
8. 6762