John Adam is a Computer Science student. His teacher gave him a homework to find a number that can be considered a binary palindrome. A number is considered a binary palindrome if it's binary representation is a palindrome. Also, the binary representation of the number must not contain any leading zeroes. Since John is poor at building logics, help John find the $N^{th}$ binary palindrome if his teacher gave him N.

Input Format:
First line contain number of test cases T.
The following T lines consist of an integer N.

Output Format:
Print $N^{th}$ binary palindrome.

Input Constraints:
$1 \leq T \leq 10^6$
$1 \leq N \leq 10^9$