Число называется свободным от квадратов, если оно не делится ни на один полный квадрат, кроме 1. Вам необходимо подсчитать их!

Входные данные

Первая строка содержит количество тестов t. Каждая из следующих t строк содержит одно натуральное число n (n ≤ 1014).

Выходные данные

Вывести t строк, каждая из которых содержит количество натуральных свободных от квадратов чисел, не больших n.