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(n\le 2\cdot 10^6)$.

Output

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

Examples