Background

Special for beginners, ^_^

Description

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

Format

Input

输入若干（不超过100万）行，每行一个不超过1e19的正整数，输入0结束。

Output

输出若干行对应的值。

Samples

1
2
3
4
78
0

2
4
5
8
83

Limitation

1s, 1024KiB for each test case.