PALIN2 - Bit Maker

no tags 

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


Added by:killerz
Date:2012-07-26
Time limit:1s
Source limit:50000B
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:My Own