Problem R
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,\underset{―}{2},4,\underset{―}{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\le i\le 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.

4
100
13
12
2018

7
1
4
2