Background

Special for beginners, ^_^

Description

石老板所在城市开设了一家奇葩银行，如果第一天某个账户存入（拥有）n枚金币。下一天，金币数量按照如下规则变化：如果n偶数，直接对折；如果n是奇数，并且满足$2^k \leq n<2^{k+1}$，则变为$\frac{(n-1)}{2} + 2^k$。问石老板想从银行取走（必须取完）m枚金币，问最少需要存入多少枚金币。 注意：只能一次性全部存入一次性全部取出，不允许多次存取部分金币薅羊毛，但是允许T+0操作。

Format

Input

每行一个正整数n($\leq 10^{36}$)，直到文件结束，表示最终提取的金币数量。 每个测试点不超过10万组数据。（提示：使用 __int128）

Output

每行输出一个最少金币数。

Samples

1
2

1
2

Limitation

1s, 1024KiB for each test case.

Source

石老板系列