题目描述

给定一个正整数 $N$ ，求最小的比 $N$ 大的正整数 $M$ ，使得 $M$ 与 $N$ 的二进制表示中有相同数目的 $1$ 。

举个例子，假如给定的 $N$ 为 $78$ ，其二进制表示为 1001110 ，包含 $4$ 个 $1$ ，那么最小的比 $N$ 大的并且二进制表示中只包含 $4$ 个 $1$ 的数是 $83$ ，其二进制是 1010011 ，因此 $83$ 就是答案。

输入格式

输入若干行，每行一个数 $N$ ，输入0结束。

输出格式

输出若干行对应的值。

样例

1
2
3
4
78
0

2
4
5
8
83

数据范围

$1≤n≤1000000$