primes-1

Egy pozitív számot mely $a b^2 c^3$ alakú, ahol $a<b<c$ prímszámok nevezzünk $123$ számnak. Hány $123$ szám van az $[1,N]$ intervallumban ($Y$)?

Bemenet specifikáció

Az első sorban van $T$ az esetek száma. Majd $T$ sor következik az $N_k ~~ (k=1\ldots T)$ számokkal.

Kimenet specifikáció

$T$ sor a keresett $Y_k~~(k=1\ldots T)$ számokkal.

Korlátok

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

1. példa bemenet

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

1. példa kimenet

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