A positive integer k is called square-free if k is not divisible by d² for any d > 1

Input

The input contains one integer t denoting the number of test cases. Each of the following t lines contain a single integer n, 1 ≤ n ≤ 10¹⁰

Output

Your program should output one integer per test case, the n-th non-square-free number.

Example

Input:
1
10

Output:
27