#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/08

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/08

Repovive

Next Binary Palindrome - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG08. Next Binary Palindrome

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given $T$ queries, each with a positive integer $N$ , find the smallest positive integer whose binary representation (without leading zeros) is a palindrome and is greater than or equal to $N$ .

A binary palindrome reads the same forwards and backwards. For example, $5 = 101_2$ , $7 = 111_2$ , and $9 = 1001_2$ are binary palindromes, while $6 = 110_2$ and $10 = 1010_2$ are not.

Constraints

$1 \le T \le 10^5$
$1 \le N \le 10^9$

Input

\begin{array}{l} T \\ N_1 \\ N_2 \\ \vdots \\ N_T \end{array}

Output

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_T \end{array}

Samples

Input

1
5

Explanation

The binary representation of $5$ is $101$ , which reads the same forwards and backwards. So $5$ is already a binary palindrome. Answer: 5.

Output

Input

1
6

Explanation

$6 = 110_2$ , not a palindrome. $7 = 111_2$ , which is a palindrome. Answer: 7.

Output

Input

Explanation

Query 1: $1 = 1_2$ , already a palindrome. Answer: 1. Query 2: $10 = 1010_2$ , not a palindrome. We check: $11 = 1011_2$ (no), $12 = 1100_2$ (no), ..., $15 = 1111_2$ (yes, palindrome). Answer: 15. Query 3: $32 = 100000_2$ , not a palindrome. $33 = 100001_2$ , which is a palindrome. Answer: 33.

Output

1
15
33

A binary palindrome reads the same forwards and backwards. For example, $5 = 101_2$ , $7 = 111_2$ , and $9 = 1001_2$ are binary palindromes, while $6 = 110_2$ and $10 = 1010_2$ are not.

Constraints

$1 \le T \le 10^5$
$1 \le N \le 10^9$

\begin{array}{l} T \\ N_1 \\ N_2 \\ \vdots \\ N_T \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_T \end{array}

The binary representation of $5$ is $101$ , which reads the same forwards and backwards. So $5$ is already a binary palindrome. Answer: 5.

$6 = 110_2$ , not a palindrome. $7 = 111_2$ , which is a palindrome. Answer: 7.