Migrated from Lutece 238 Wonderful Infinite Number

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

People in Tribe Infinite honor numbers $3, 5, 7$ for their lucks. An integer is considered an Infinite Number if its prime factors are only among $3, 5, 7$. (Note: $3, 5, 7$, at least one and any is OK.) Everyone in the tribe has his/her Infinite Number as a personal ID. When a new infant comes, he/she will be given the minimal Infinite Number which is not have been used. (If a number is allocated to someone, it will belong to him/her permanently. So death and leaving are needless to worry about). Unfortunately, due to Evil Leileijj's damage, the birth log of Infinite is missing. No one knows what the next Infinite Number is. And the worst is, prince xqq will be given birth and the king may fail to give his son an Infinite Number. At the very moment, Charleszy, the cleverest man in the tribe, claims that totally $N$ people have been born since the tribe was founded. Your task is to help the king get xqq's Infinite Number.

Note: according to the rules, people at the beginning are numbered $3, 5, 7, 9, 15 \cdots$Suppose there are $5$ people already, the next Infinite Number, after $15$, is $21$.

Input

There are multiple cases. The first line is an integer $T(1 \leq T \leq 10)$, which is the number of cases. Each case has an integer $N(0 \leq N \leq 99999)$, indicating that $N$ people have been born since the beginning.

Output

For each case, output xqq's Infinite Number.

Samples

4
0
1
3
5

3
5
9
21

Note

The result may be extremely large, greater than $2^{64}$.

Resources

第四届北京邮电大学程序设计竞赛决赛