Y Practice Set - Prime Numbers

#### Start

2020-07-17 15:00 AKDT

## Y Practice Set - Prime Numbers

#### End

2020-07-24 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -70 days 12:56:17

166:00:00

0:00:00

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