Різні прості

Щасливими називаємо додатні цілі числа, які мають щонайменше три різні прості дільники. Наприклад, $30$ і $42$ — це перші два щасливих числа. Для заданого натурального числа $n$ потрібно знайти $n$-те щасливе число.

Вхідні дані

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

Вихідні дані

Виведіть $t$ рядків, у кожному з яких буде щасливе число для відповідного тесту.

Приклади