# Non-Prime Factors

In many programming competitions, we are asked to find (or
count the number of) Prime Factors of an integer $i$. This is boring. This time, letâ€™s
count the number of Non-Prime Factors of an integer
$i$, denoted as `NPF(i)`.

For example, integer $100$ has the following nine factors:
$\{ 1, \underline{2}, 4,
\underline{5}, 10, 20, 25, 50, 100\} $. The two which
are underlined are prime factors of $100$ and the rest are non-prime
factors. Therefore, `NPF(100)` =
$7$.

## Input

The first line contains an integer $Q$ ($1 \le Q \le 3\cdot 10^6$) denoting the number of queries. Each of the next $Q$ lines contains one integer $i$ ($2 \leq i \leq 2\cdot 10^6$).

## Output

For each query $i$,
print the value of `NPF(i)`.

## Warning

**The I/O files are large. Please use fast
I/O methods.**

Sample Input 1 | Sample Output 1 |
---|---|

4 100 13 12 2018 |
7 1 4 2 |