You may be familiar with the palindrome, i.e. a number whose reverse is the same as that of the original number. For example 5115 is a palindrome since its reverse is 5115. So now your task is to find minimum possible number whose binary equivalent is a palindrome.

For Example: if input is 4 (with binary equivalent 100) then the output is 5 (with binary equivalent 101).

Input

Input starts with 't' the number of test cases, 1 <= t <= 1000.

Then followed by t lines with numbers N, 1 <= N <= 10^18.

Output

Display the minimum possible number greater than N whose binary equivalent number is a palindrome.

Example

Input:
3
4
8
12

Output:
5
9
15