403160: GYM101055 C It-miha

In ancient Egypt, the construction of the pyramids is surrounded by mystery. Many researchers consider that the technology necessary to build them wasn't available at the time, and suspect that the Egyptian had extraterrestrial help to build them.

An example of those mysteries are the "It-miha" numbers. In the Egyptian province of It-miha was found a stone engraved with a sequence of numbers. Apparently the numbers had no link, until Poincaré, in the end of the XIX century, conjectured that the numbers written on that stone were the 500 first numbers that have no perfect square divisors.

A perfect square is a number is a number that has an integer square root, like 1, 4, 9, 16, 25, etc. We say a number is free of perfect square divisors if it is not divisible by any perfect square greater than 1.

It may seem simple to us, today, to determine such numbers, but we must remember that in that time, more than 3500 years ago, even the number system was different, and it made any calculation very difficult.

The "It-miha" numbers are very frequent in pyramids construction. The base of the Quéops pyramid, for example, is 210 × 210 and its height is 105 meters. All its dimensions are "It-miha" numbers!!!

The first ten "It-miha" numbers are 1, 2, 3, 5, 6, 7, 10, 11, 13 and 14. Your task is to, given an integer N, determine the Nth "It-miha" number.

The first line has a single integer Q, the number of queries.

Each of the next Q lines has an integer N.

Limits

• 1 ≤ Q ≤ 25
• 1 ≤ N ≤ 2·10¹⁰

For each query, print the Nth "It-miha" number.

5
1
2
4
12
371

1
2
5
17
609