n-те вільне від квадратів#6352
Натуральне число називається вільним від квадратів, якщо воно не ділиться на жодний квадрат числа, більший за . Наприклад, першими числами, вільними від квадратів, будуть \{1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, \ldots\}. Знайдіть -те найменше вільне від квадратів число.
Перший рядок містить кількість тестів . Кожен з наступних рядків містить одне натуральне число (1 \le n \le 10^9).
Для кожного тесту вивести в окремому рядку -те найменше число, вільне від квадратів.
Приклад 1