Задачі
Различные простые
Различные простые
Счастливыми назовем положительные целые числа, которые имеют хотя бы три различных простых делителя. Например $30$ и $42$ первые два счастливых числа. По заданному натуральному числу $n$ следует найти $n$-ое счастливое число.
\InputFile
Первая строка содержит количество тестов $t$. Каждая из следующих $t$ строк содержит одно целое число $n~(n \le 2 \cdot 10^6)$.
\OutputFile
Выведите $t$ строк, каждая из которых содержит счастливое число для соответствующего теста.
Вхідні дані #1
2 1 2
Вихідні дані #1
30 42