When Changu was introduced to the concept of prime numbers, he was so glad that, after one days happy work, he was able to generate the first thirteen prime numbers. He has the ability that, given any number, he can tell whether or not it is divisible by any of the first thirteen primes. The first thirteen prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41; their product is 304250263527210. A number is called 'mangu' if it is divisible by at least one of the first thirteen primes. Thus, the first number that is not 'mangu' is 1, and the second is 43. Changu wrote all the 'mangu' numbers in ascending order in a list.

Your task is to find out, given k, what is the k-th element in the list.

Input

The first line contains T (not more than 500), the number of test cases. In each case there is a single number k.

Output

For each test case, output the k-th mangu number on a single line. You may assume that the answer is never bigger than 304250263527210.

Example

Input:
2
2
3

Output:
3
4