Число називається вільним від квадратів, якщо воно не ділиться на жодний повний квадрат, окрім 1. Вам необхідно підрахувати їх!
Перший рядок містить кількість тестів t. Кожний з наступних t рядків містить одне натуральне число n (n ≤ 10^14
).
Вивести t рядків, кожен з яких містить кількість натуральних вільних від квадратів чисел, не більших n.