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