Square Free Numbers
Very easy
Execution time limit is 3 seconds
Runtime memory usage limit is 128 megabytes
The integer is called square-free if it is not divisible by a perfect square, except 1. You have to count them!
Input
First line contains the number of test cases t. Each of the following t lines contains one positive integer n (n ≤ 10^14).
Output
Print t lines, each line contains the number of positive square-free integers not larger than n.
Examples
Input #1
Answer #1
Submissions 496
Acceptance rate 39%