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

Вхідні дані

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

Вихідні дані

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