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