In number theory we call an integer square-free if it is not divisible by a perfect square, except 1. You have to count them!

Input

First line contains an integer T, the number of test cases (T≤100). The following T lines each contains one positive integer: n, where n ≤ 10¹⁴

Output

T lines, on each line output the number of (positive) square-free integers not larger than n.

Example

Input:
3
1
1000
100000000000000

Output:
1
608
60792710185947

Warning: A naive algorithm probably not works.