Translate

Thursday, December 19, 2013

c c++ c# binary number

The binary weight of a positive integer is the number of 1's in its binary representation. For example, the decimal number 1 has a binary weight of 1, and the decimal number 7 (which is 111 in binary) has a binary weight of 3.

Given a positive integer N, find the smallest integer greater than N that has the same binary weight as N.

INPUT
The first line of input contains a number T the number of test cases. The next T lines contain a number N.

OUTPUT
For each test case output a line containing the smallest number greater than N which has the same binary weight as N.

CONSTRAINTS
1 <= N <= 10000

SAMPLE INPUT
2
3
7

SAMPLE OUTPUT
5
11