Shil has a number X.He challenges you to find minimum positive number K such that F(K) is equal to X.

F(x) is defined as 1^2^3^....x. ^ denotes the bitwise Xor operation

Input

First line of input will consists of total number of test cases T.Next T lines contains a number X.

Output

For each test case , output minimum possible value of K such that F(K) is equal to X.If there is no such K , print -1.Note that K should be positive number.

Constraints

1 ≤ T ≤ 1000000
0 ≤ X ≤ 10^18

Example
Input:
3
1
2
100

Output:
1
-1
100

Explanation
F(1)=1 , F(100)=100 and there is no such K such that F(K)=2

见题面

见题面