题目描述

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

输入格式

输入若干行，每行一个数 $n$ ($1 \leq n \leq 1000000$)，输入"0"结束。

输出格式

输出若干行对应的值。

样例

输入样例1

1
2
3
4
78
0

输出样例1

2
4
5
8
83