Go'zal sonlar

Go'zal son deb, $p^q$ ko'rinishida tasvirlanadigan sonlarga aytiladi, bu yerda $p$ va $q$ tub sonlar. Masalan, $4 = 2^2$ --- go'zal son, $343 = 7^3$ --- go'zal son, biroq $10$ va $42$ go'zal sonlar emas.

Sizga $Q$ ta so'rovning har birida $N$ soni beriladi. Vazifangiz $[1 \ldots N]$ oralig'idagi go'zal sonlar nechta ekanligini topish.

### Input Format

Birinchi qatorda bitta butun son $Q$ $(1 \leq Q \leq 10^5)$ kiritiladi.

Ikkinchi qatorda $Q$ ta butun son --- navbatdagi so'rov uchun $N$ $(1 \leq N \leq 10^9)$ soni kiritiladi.

### Output Format

$Q$ ta so'rovning har biri uchun so'rov natijasini probel bilan ajratib chiqaring.

### Scoring

{|c|c|c|}

\hline

**Subtask** & **Cheklov** & **Ball**

\hline

1 & $Q \leq 100$, $N \leq 1000$ & 2

\hline

2 & $N \leq 1000$ & 3

\hline

3 & Qo'shimcha cheklovlarsiz & 5

\hline

### Notes

Birinchi misolda $N=3$ uchun: $[1,3]$ da $0$ ta go'zal son bor; $N=7$ uchun: $1$ ta ($4$); $N=10$ uchun: $3$ ta ($4$, $8$, $9$).

Ikkinchi misolda $N=40$ uchun: $6$ ta go'zal son bor.