A function f is defined over natural numbers as:

f(N) = ∑ d_i μ(d_i)

Here the summation is over d_i, all positive integers which are factors of N.

μ(n) is the Möbius function defined in the following way: If there exists a prime p such that p² is a factor of n, then μ(n)=0. Otherwise, if n has an odd number of prime factors, μ(n)=-1. If not, μ(n)=1. Thus the first few values for μ(n) (starting from 1) are 1, -1, -1, 0, -1, 1, -1, 0...

Given an integer X (0 <= X <= 10¹²), find the smallest natural number N such that |f(N)|>X.

Input

The first line of the input contains T, the number of test cases (T <= 1000). Following this are T lines, each containing an integer X (0 <= X <= 10¹²) corresponding to the test case.

Output

For each test case in the input, output the smallest natural number N such that |f(N)|>X.

Example

Input:
2
1
2

Output:
3
5