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 answer for each problem in a separate line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 1010

Sample Input:
4
5
4
9
7

Sample Output:
4
3
8
-1