In NumboLand, all the houses have kitties. The house numbered n will have a kitty of type k, if and only if house k doesn't have more than 1 type of kitty and the number n is divisible by k. For example house 30 can only have kitties of type 2, 3 and 5. If you wonder why 1 is not there, note that house 1 is the kitty playground and you can find all type of kitties there.

House 3 will have only kitty of type 3. Because 3 divides 3 and it's not possible to have another type of kitty in that house maintaining the criteria. Same thing is true for house 5,11,19. Euclid proved that there are infinite number of houses who will have exactly one kitty. Everyone of NumboLand were excited when he did that. They threw a BIG party for that!

The owner of house n wants to visit other houses with all his kitties. He will not go to any house that has bigger number than his house. But there is a big problem, if he goes to any house that has the same type of kitties that he has, they'll start playing together and leave for kitty playground. And he doesn't want that to happen.

Can you tell the owner of house n, how many houses he can visit without having this incident?

Input

A single number t, number of test cases. After that there will be t lines, each containing one number n (2<=n<=1000000).

Output

For each case, output how many houses that owner can visit without losing any of his kitties.

Example

Input:
5
2
3
4
17
100

Output:
0
1
1
15
39