The Next Integer with the Same Number of 1s

Problem Description

Given a positive integer $N$, find the smallest positive integer $M$ greater than $N$ such that the binary representations of $M$ and $N$ contain the same number of $1$s.

For example, given $N=78$, its binary representation is $1001110$, which contains $4$ ones. The smallest number greater than $N$ whose binary representation also contains exactly $4$ ones is $83$ (binary $1010011$), so $83$ is the answer.

Input Format

There are several lines of input. Each line contains one integer $n\ (1\le n\le 1000000)$. Input ends with 0.

Output Format

For each input line, output the corresponding answer on its own line.

Sample Input

1
2
3
4
78
0

Sample Output

2
4
5
8
83

Hint

Source: ybt (一本通 online judge).