Числа, вільні від квадратів

Число називається вільним від квадратів, якщо воно не ділиться на жодний повний квадрат, окрім 1. Вам необхідно підрахувати їх!

Вхідні дані

Перший рядок містить кількість тестів t. Кожний з наступних t рядків містить одне натуральне число n (n ≤ 10^14).

Вихідні дані

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

Приклади