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