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