n-те вільне від квадратів

Натуральне число називається вільним від квадратів, якщо воно не ділиться на жодний квадрат числа, більший за 1. Наприклад, першими числами, вільними від квадратів, будуть {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, ...}. Знайдіть n-те найменше вільне від квадратів число.

Вхідні дані

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

Вихідні дані

Для кожного тесту вивести в окремому рядку n-те найменше число, вільне від квадратів.

Приклади