Problem Description

In computer science, bitwise AND ($\operatorname{and}$) is a binary operation. For any non-negative integers $a$ and $b$, let their binary representations be $a = \sum_{i=0}^{\infty} a_i 2^i$ and $b = \sum_{i=0}^{\infty} b_i 2^i$, where $a_i, b_i \in \{0,1\}$ and only finitely many of them are non-zero. We define the result of the bitwise AND operation between $a$ and $b$, denoted as $a \operatorname{and} b$, as:

$$a \operatorname{and} b = \sum_{i=0}^{\infty} (a_i \cdot b_i) 2^i$$

In mathematics, divisibility ($\mid$) is a binary relation. For any positive integers $a$ and $b$, if and only if there exists a positive integer $k$ such that $a = b \cdot k$, we say that $b$ divides $a$, written as $b\mid a$.

In mathematics, the greatest common divisor ($\gcd$) is a binary operation. For any positive integers $a$ and $b$, we define their greatest common divisor $\gcd(a,b)$ as the largest positive integer that divides both $a$ and $b, i.e.$:

$$\gcd(a, b) = \max\{ d \in \mathbb{N}^+ : d \mid a \wedge d \mid b \}$$

Now you are given a positive integer $x$. Please find the smallest positive integer $y$ such that the result of the bitwise AND operation on $x$ and $y$ is equal to the greatest common divisor of $x$ and $y$. That is, compute:

$$y_{\min} = \min\{ y \in \mathbb{N}^+ : (x \operatorname{and} y) = \gcd(x, y)\}$$

Input Format

This problem contains multiple test cases. The first line contains a positive integer $T$ ($1\le T\le 10^5$), representing the number of test cases.

Next are the descriptions of $T$ test cases.

Each test case consists of one line containing a positive integer $x$ ($1 \le x < 2^{60}$).

Output Format

For each test case, output one line containing a positive integer $y_{\min}$, where $y_{\min} = \min\{ y \in \mathbb{N}^+ : (x \operatorname{and} y) = \gcd(x, y)\}$.

4
9
16
3108
56109

1
16
4
1

Hint

Translated by ChatGPT 5