Rasta Thamaye Dilo
Description
Jubayer is a nice and talented kid. He is a two times ICPC World Finalist. He used to utilize his time solving problems after problems. But after all those years of hard work and achievements, he decides to enjoy a tiny break from his daily routine and roam to the villages of his very own B.Baria district. So, he went to B.Baria. But he soon became very fed up as he saw he cannot go to every village in his district as there are not enough roads that can help him reach every village. Also, a weird pattern was caught to the attention of this great programmer. In his district, there are $n-1$ villages. The villages are named with natural numbers (don't ask me why, I am just a simple problem setter). For some weird reason, there is no village numbered as $1$. Villages are named from $2$ to $n$ (for example: if $n=5$ then name of the villages are $2$, $3$, $4$ and $5$). And there is a road connecting the village $i$ and the village $j$ if and only if either $i$ is divisible by $j$, or $j$ is divisible by $i$.
Now, Jubayer wishes to create some new roads to extend the reachability: he wants to connect every village and roam everywhere without any hassle. But he is failing to determine the minimum number of roads that he needs to construct in order to fulfill this purpose. Now it is your turn to help this world famous programmer.
First line will be number of test cases, $T\space(1 \le T \le 10^5)$.
Next $T$ lines will have a number $n\space(2 \le n \le 10^7)$ denoting the name of the last village in the district.
For each test case, print the minimum number of roads needed to connect all the villages in a single line.
Input
First line will be number of test cases, $T\space(1 \le T \le 10^5)$.
Next $T$ lines will have a number $n\space(2 \le n \le 10^7)$ denoting the name of the last village in the district.
Output
For each test case, print the minimum number of roads needed to connect all the villages in a single line.
2
2
5
0
2
Note
Use faster input/output.
Explanation of the second test case: Here $n = 5$, so the villages are named $2,3,4,5$. There's already an edge between $2$ and $4$ because $2$ divides $4$.
You have to construct at least $2$ roads to make every village reachable to every other (via some roads).