URI Online Judge | 1338

It-Miha

XIV Maratona de Programacao IME-USP, Brazil

Timelimit: 6

In Ancient Egypt, the building of the pyramids is surrounded in mystery. Many researchers consider that the technology needed to build them wasn't available at the time, and suspect that the egyptians had extraterrestrial help to build them. An example of those mysteries are the "It-miha" numbers. In the egyptian province of It-miha, a rock with an inscripted sequence of numbers was found. Apparently the numbers had no connection to each other, until Poincaré, at the end of the 19th century, conjectured that the recorded numbers were the first 500 square-free integers. A perfect square is an integer with an integer square root, such as 1, 4, 9, 16, 25, etc. We say that an integer is square-free if it isn't divisible by any perfect square greater than 1. It may sound simple to us today to determine those numbers, but over 3500 years ago, with a different numbering system, the calculations were very difficult to perform. The "It-miha" numbers are also very frequent in the design of the pyramids. The Queops pyramid, for instance, has a base of 210 x 210 and height of 105 meters. All dimensions are "It-miha" numbers!!!

The first ten "It-miha" numbers are 1, 2, 3, 5, 6, 7, 10, 11, 13, 14. Your task in this problem is, given N, find the N-th "It-Miha" number.

Input

The input has several test cases. The first line of the input contains an integer T corresponding to the number of cases. The first (and only) line of each test case contains an integer N, 1 ≤ N ≤ 20 000 000 000.

Output

For each test case, print a line containing the N-th square-free integer.

Sample Input Sample Output

5
1
2
4
12
371

1
2
5
17
609