The binary weight of a positive integer is the number of 1's in its binary representation.for example,the decmial number 1 has a binary weight of 1,and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.Give a positive integer N,return the smallest integer greater than N that has the same binary weight as N.N will be between 1 and 1000000000,inclusive,the result is guaranteed to fit in a signed 32-bit interget.
Samebinaryweight
Input
The input has multicases and each case contains a integer N.
Output
For each case,output the smallest integer greater than N that has the same binary weight as N.
Sample Input
1717
4
7
12
555555
Sample Output
1718
8
11
17
555557