You are given the binary representation of a number. You must consider the highest number of set bits in the binary representation to complete your task. For example, $23$ is represented as $10111$ in binary and it contains four set bits (1-bits). You are also given a number $N$ and your task is to determine the number that is less than or equal to $N$ and contains the maximum number of set bits in its binary representation. 

In other words, print a number $K$ that is less than or equal to $N$ such that the number of set bits in the binary representation of $K$ must be maximum

Input format

• First line: An integer $t$ denoting the number of test cases
• For each test case:
  • First line: An integer $N$

Output format

For each test case, print the answer on a new line denoting a number $K$ that is less than or equal to $N$ such that the number of set bits in the binary representation of $K$ must be maximum.  

Constraints

$1 ≤ t ≤ 1000\\ 1 ≤ N ≤ 10^9$