The integer is called square-free if it is not divisible by a perfect square, except 1. You have to count them!
First line contains the number of test cases t. Each of the following t lines contains one positive integer n (n ≤ 10^14).
Print t lines, each line contains the number of positive square-free integers not larger than n.