n-ое свободное от квадратов

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

Входные данные

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

Выходные данные

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

Примеры