说明

Rei最近在玩一款叫天天打飞机的小游戏。在这款游戏中，战机需要通过合成来变强

战机的合成规则很简单：2架1级的飞机可以合成1架2级的飞机，2架2级的飞机可以合成1架3级的飞机，...。

系统每分钟会送Rei一架1级的飞机，而因为Rei很勤奋，他会一直守在电脑前面合成任何能合成的飞机。

Rei等啊等，等了大概有1145141919180分钟，虽然他尽可能的将所有飞机合成了，但是他面前有很多很多的飞机，所以他想知道他到底有多少架飞机。

具体而言，他会问你：当系统送了他x架1级飞机后，经过合成，他会剩余多少架飞机。

输入格式

一个整数x表示系统送了$x$架1级的飞机。

输出格式

一个整数，表示最后剩余多少架飞机。

样例

10

2

31

5

提示

对于样例1：经过合成，最后剩下1架2级飞机，1架4级飞机。
对于样例2：经过合成，最后剩下1架1级飞机，1架2级飞机，1架3级飞机，1架4级飞机，1架5级飞机。
对于50%的数据，满足1≤n≤2000
对于100%的数据，满足1≤n≤10⁹