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. \InputFile 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)$. \OutputFile Print $t$ lines, each containing the corresponding lucky number for that test case.