With full zeal, Daenerys Targaryen is looking to conquer the seven kingdoms. In need of wise commanders, she wants them to solve the below problem:

Given the following function F and an integer N find the smallest integer x satisfying F(x) = N.

If no such x exists, print “-1”. (without quotes)

Input Format:

The first line contains one integer T, the number of times she gives you the problem.

T lines follow, each containing a single integer N.

Output Format:

Print the answer for each problem in a separate line.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10¹⁰

Sample Input:

4

5

4

9

7

Sample Output:

4

3

8

-1