Beautiful Numbers

Тавсифи масъала

A number is called beautiful if it can be represented in the form $p^q$, where $p$ and $q$ are prime numbers. For example, $4 = 2^2$ is beautiful, $343 = 7^3$ is beautiful, but $10$ and $42$ are not beautiful.

You are given $Q$ queries. In each query, you are given a number $N$. Your task is to find how many beautiful numbers exist in the range $[1 \ldots N]$.

Input Format

The first line contains a single integer $Q$ $(1 \leq Q \leq 10^5)$.

The second line contains $Q$ integers --- the value $N$ $(1 \leq N \leq 10^9)$ for each query.

Output Format

For each of the $Q$ queries, print the answer separated by spaces.

Scoring

Notes

In the first sample, for $N=3$: there are $0$ beautiful numbers in $[1,3]$; for $N=7$: there is $1$ beautiful number ($4$); for : there are beautiful numbers (, , ).

In the second sample, for $N=40$: there are $6$ beautiful numbers.

3
3 7 10

0 1 3

1
40

6