Limits
2s, 512 MB

Recently **Hasinur** The Great is dating a girl. Getting inspired from Hasinur's coding skill , she decided to be a programmer too. But, as she is not so experienced she can't write program so efficiently . Recently she tried an problem that Hasinur gave her to solve but got **TLE** (Time Limit Exceeded ) . Now , let me introduce you with the dark side of Hasinur The Great. He is a mad programmer. He is very nice and gentleman. But if his girlfriend can't solve problem that he gives her, he becomes very angry. Now as you are a well wisher of Hasinur and his family , please help his girlfriend. She wrote the code given below:

```
#include<bits/stdc++.h>
using namespace std;
int IsPrime(int a)
{
int x;
for(x = 2; x < a; x++){
if(a % x == 0)
return 0;
}
return 1;
}
int DistinctPrimeCount(int n)
{
int i, j = 0;
for(i = 2; i <= n; i++){
if(n % i == 0)
j += IsPrime(i);
}
return j;
}
int main()
{
int N, M, i, j, k;
scanf("%d", &N);
for(i = 0; i < N; i++){
scanf("%d", &M);
printf("%d\n",DistinctPrimeCount(M));
}
}
```

Nothing hard , you have to make this code efficient so that it gets accepted for **N ≤ 5000000** and **M ≤ 5000000.**

In first line there will be an integer **N**. And then there will be N lines, each containing an integer **M**.

**1 ≤ N ≤ 5000000****0 ≤ M ≤ 5000000**

Print an integer for each input **M**, the output of the given code.

Input | Output |
---|---|

2 1 2 | 0 1 |