2018 ICPC Asia Singapore Regional Contest

#### Start

2018-12-12 16:00 AKST

## 2018 ICPC Asia Singapore Regional Contest

#### End

2018-12-12 21:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1039 days 22:12:26

5:00:00

0:00:00

# Problem LNon-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