Description

零零数是指 一个数的二进制下 0的个数大于1的个数的数。现在你有一个数 $n$ ，你可以进行神秘的操作使得 $n = n + 1$。询问最少操作几次，可以使得 $n$ 变为零零数。

Input

第一行一个整数 $n$ 表示需要变为零零数的值。

Output

输出一个整数 $m$ 表示最少操作的次数。

Samples

4

0

5

3

样例解释

例如：4的二进制表示为100，其中0有 $2$ 个，1有 $1$个，其0的个数大于1的个数，所以为零零数。 5的二进制表示为101，其中0有 $1$ 个，1有 $2$个，其0的个数小于1的个数，所以不为零零数。

数据范围

对于 100%的数据: $1 \le n \le 10^{16}$