Yesterday NETA got placed and was getting bored as he was all free. For passing his time he wrote a number A on a paper. He then added the number of ones in the binary representation of the number to that number and formed a new number B. He kept doing the process infinitely. So he got a chain of numbers say A -> B -> C -> D ...so on.
In this Chain B is said to be associated with A, C with A & B both, D with A, B & C all and so on. He observed something and asked a question to you that given a number N you need to tell the maximum number with which N is associated.

Input:
First line of the input contains a single integer T denoting number of test cases.
For each test case, one line containing one integer N.

Output:
For each test case, print a single line containing required number. If N is not associated to any number print -1.

Constraints:

• 1<= T <= 5000
  
• 1<= N <= 10^18
  

Sample Input:
3
3
4
5

Sample Output:
2
-1
4