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
def main():
    for _ in xrange(input()):
        X = input()
        if X == 0:
            print 3

        else:
            if X == 1:
                print 1
            else:
                if X % 4 == 0:
                    print X
                elif (X - 3) % 4 == 0:
                    print X - 1
                else:
                    print -1

if __name__ == '__main__':
    main()