Различные простые

Счастливыми назовем положительные целые числа, которые имеют хотя бы три различных простых делителя. Например $30$ и $42$ первые два счастливых числа. По заданному натуральному числу $n$ следует найти $n$-ое счастливое число.

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

Первая строка содержит количество тестов $t$. Каждая из следующих $t$ строк содержит одно целое число $n(n\le 2\cdot 10^6)$.

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

Выведите $t$ строк, каждая из которых содержит счастливое число для соответствующего теста.

Примеры