题目描述

给定一个正整数 $x$，请找出最小的正整数 $y$，使得 $x$ 和 $y$ 进行按位与（$\operatorname{and}$）运算的结果，等于 $x$ 和 $y$ 的最大公约数（$\gcd$）。

换言之，你需要求解满足以下方程的最小正整数 $y$：

输入格式

第一行包含一个正整数 $T$ —— 表示测试用例的数量。

接下来 $T$ 行，每行包含一个正整数 $x$ —— 表示给定的数值。

输出格式

对于每个测试用例，输出一行一个正整数，表示符合条件的最小正整数 $y$。

样例输入 1

4
9
16
3108
56109

样例输出 1

1
16
4
1

说明

数据范围

• 对于所有测试点，保证 $1 \le T \le 10^5$。
• 对于每个测试用例，保证 $1 \le x < 2^{60}$。
• 保证所有的输入数值均为整数。