题目描述

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

例如，$N=78$，其二进制表示为 $1001110$，包含 $4$ 个 $1$。比 $78$ 大且二进制中恰好有 $4$ 个 $1$ 的最小数是 $83$（二进制 $1010011$），因此答案为 $83$。

输入格式

输入包含多行，每行一个正整数 $n$。当输入为 $0$ 时结束。

输出格式

对于每个输入的 $n$（除了结束的 $0$），输出一行一个整数，表示对应的 $M$。

样例

1
2
78
0

2
4
83

数据范围与提示

• $1 \le n \le 10^6$
• 输入以 $0$ 结束，不处理 $0$。