Amit likes to play with prime numbers. He is also very careful about his health and goes to gym regularly. After hard work of two years, Amit is able to lift weights that are prime numbers but less than 50.
Yogesh, being his good friend, challenges him to find the k'th number whose at least one prime divisor is less than 50.
First line contains a single integer t denoting the number of test cases.
Each of the next t lines contains a single integer k.
For each testcase, print a single line containing required output.
It is guaranted that the answer is less than or equal to 10^18.
1 <= t <= 5
1 <= k <= 5*10^17
10% score :
1 <= k <= 10
40% score :
1 <= k <= 10^5
100% score :