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