题目描述

这是一个关于二进制的问题。

给定一个正整数 $x$，你需要找到一个最小的正整数 $y$，满足:

• $x≤y$。
• $y$ 在二进制表示下 $1$ 的个数为偶数。

对于第二个条件，例如：

• $4$ 的二进制表达是 $(100)_2$，不满足。
• $5$ 的二进制表达是 $(101)_2$，满足。

输入格式

第一行输入一个正整数 $T(1≤T≤10^5)$ 代表询问的个数。

对于每组询问，输入一行一个正整数 $x(1≤x≤10^9)$ 代表一个询问。

输出格式

输出 $T$ 行每行一个数代表答案。

3
2
5
6

3
5
6