题目描述

在计算机科学中，按位与（$\operatorname{and}$）是一种二元运算。对于任意的非负整数 $a$ 和 $b$，设其二进制表示为 $a = \sum_{i=0}^{\infty} a_i 2^i$，$b = \sum_{i=0}^{\infty} b_i 2^i$，其中 $a_i, b_i \in \{0,1\}$ 仅有有限个非零，我们记 $a$ 和 $b$ 进行按位与运算的结果 $a \operatorname{and} b$ 为：

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

在数学中，整除（$\mid$）是一种二元关系。对于任意的正整数 $a$ 和 $b$，当且仅当存在一个正整数 $k$，满足 $a = b \cdot k$，我们称 $b$ 整除 $a$，记作 $b\mid a$。

在数学中，最大公约数（$\gcd$）是一种二元运算。对于任意的正整数 $a$ 和 $b$，我们记 $a$ 和 $b$ 的最大公约数 $\gcd(a,b)$ 为最大的能同时整除 $a$ 和 $b$ 的正整数，即：

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

现在有一个正整数 $x$，请找出最小的正整数 $y$，使得 $x$ 和 $y$ 进行按位与运算的结果等于 $x$ 和 $y$ 的最大公约数。即求解：

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

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le 10^5$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例共一行，包含一个正整数 $x$（$1 \le x < 2^{60}$）。

输出格式

对于每个测试用例，输出一行，包含一个正整数 $y_{\min}$，表示 $y_{\min} = \min\{ y \in \mathbb{N}^+ : (x \operatorname{and} y) = \gcd(x, y)\}$。

4
9
16
3108
56109

1
16
4
1