Description

Given a positive integer N, find the smallest positive integer M greater than N such that M and N have the same number of 1's in their binary representations.
For example, if the given N is 78, its binary representation is 1001110, which contains 4 ones. The smallest number greater than 78 with exactly 4 ones in its binary representation is 83, whose binary is 1010011. Therefore, the answer is 83.

Input Format

The input consists of several lines, each containing a number n (1 ≤ n ≤ 1000000). The input ends with a line containing 0.

Output Format

Output the corresponding value for each input line.

1
2
3
4
78
0

2
4
5
8
83