e-olymp
Problems

Distinct Primes

Distinct Primes

Lucky Numbers are those positive integers that have at least three distinct prime factors. For example 30 and 42 are the first two. You are given a positive integer n, and was asked to find the n-th lucky number.

Input

The first line contains the number of test cases t. Each of the next t lines contains one integer n (n2 * 106).

Output

Output t lines, each containing the corresponding lucky number for that test case.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
1
2
Output example #1
30
42