给定一个整数X，求出一个整数Y满足以下条件：

1.X<=Y

2.Y在二进制表示下有偶数个1

3.Y在满足上述两个条件的所有数中最小

比如4的二进制为(100)，有1个1；9的二进制为(1001)，有两个1.

多组样例测试。

第一行一个整数T(Y<=3000)，表示测试组数。

接下来T行，第i行一个整数表示Xi(Xi<=1e9)。

输出T行。

第i行一个整数Yi，表示满足Xi的数。

4的二进制(100)

5的二进制(101)