Jánošík，又名罗宾汉，劫富济贫。他和他的团伙抢劫了一支运往伯爵城堡的黄金车队，并获得了 $n$ 个宝箱。将战利品运回洞穴后，发现第 $i$ 个宝箱（对于 $i = 1, 2, \dots, n$）恰好包含 $i$ 袋金币。

如果有穷人来找 Jánošík 请求几枚金币，Jánošík 会执行以下程序：首先，他选择一个包含金币袋数量最少的非空宝箱。如果该宝箱恰好只有一袋金币，Jánošík 就把它交给那个有需要的人，并看着他高兴地离开。否则，如果宝箱里的金币袋数量是奇数，Jánošík 会把其中一袋金币放进自己的口袋，然后重新开始整个过程。然而，如果宝箱里的金币袋数量是偶数，Jánošík 会取出其中恰好一半的金币袋，并将它们放入一个空的宝箱中（幸运的是，洞穴里有很多空宝箱），然后重新开始整个过程。因此，如果一个身无分文的人来找 Jánošík，且 Jánošík 手中至少还有一个非空宝箱，那么经过（可能多次）执行 Jánošík 的程序，穷人一定能得到一袋金币。穷人会一直来到 Jánošík 的洞穴，直到所有宝箱都被清空。

Jánošík 团伙的其他强盗想知道，他们的首领这种行为是否会毁了强盗的名声。他们想知道，当所有宝箱都被清空时，Jánošík 的口袋里总共剩下了多少袋金币。

输入格式

输入的第一行也是唯一一行包含一个整数 $n$ ($1 \leqslant n \leqslant 10^9$)，表示 Jánošík 团伙抢劫的宝箱数量。

输出格式

输出的第一行也是唯一一行包含一个整数，表示在清空所有宝箱后，Jánošík 口袋中剩余的金币袋数量。

样例

输入 1

5

输出 1

2