In number theory, Euler's totient function $\varphi(n)$ counts the positive integers up to a given integer $n$ that are relatively prime to $n$. It can be defined more formally as the number of integers $k$ in the range $1\leq k\leq n$ for which the greatest common divisor $\gcd(n, k)$ is equal to $1$.
For example, $\varphi(9) = 6$ because $1, 2, 4, 5, 7$ and $8$ are coprime with $9$. As another example, $\varphi(1) = 1$ since for $n = 1$ the only integer in the range from $1$ to $n$ is $1$ itself, and $\gcd(1, 1) = 1$.
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than $1$ and itself. So obviously $1$ and all prime numbers are not composite number.
In this problem, given integer $k$, your task is to find the $k$-th smallest positive integer $n$, that $\varphi(n)$ is a composite number.

The first line of the input contains an integer $T(1\leq T\leq100000)$, denoting the number of test cases.
In each test case, there is only one integer $k(1\leq k\leq 10^9)$.

For each test case, print a single line containing an integer, denoting the answer.