Задачи
Числа, свободные от квадратов
Числа, свободные от квадратов
Число называется свободным от квадратов, если оно не делится ни на один полный квадрат, кроме 1. Вам необходимо подсчитать их!
Входные данные
Первая строка содержит количество тестов t. Каждая из следующих t строк содержит одно натуральное число n (n ≤ 1014
).
Выходные данные
Вывести t строк, каждая из которых содержит количество натуральных свободных от квадратов чисел, не больших n.
Входные данные #1
3 1 1000 100000000000000
Выходные данные #1
1 608 60792710185947