在数字电路工程中，计算算法是通过操作部件来实现的。一个操作部件具有一个或多个输入以及一个唯一的输出。不同类型的部件执行不同的数学运算。输入和输出端的值均为整数。输出端的值由部件的类型及其输入值决定。

通常，一个用于复杂运算的电路可以由更简单运算的部件构建而成。在这种情况下，每个部件的输入必须接收来自另一个部件的输出或来自电路输入端之一的值。电路中禁止出现环路依赖：部件输入端的值不能直接或间接地依赖于该部件输出端的值。任何部件输出端的值都可以传输给任意数量的其他部件的输入端。电路中某一个部件的输出值被指定为整个电路的输出值。

在本题中，需要构建一个乘以指定常数 $N$ 的乘法器电路。该电路有且仅有一个输入，接收值 $x$。电路最终的输出值必须为 $N \cdot x$，即输入值 $x$ 乘以 $N$ 的积。允许使用以下类型的部件：

1. 加法部件：有两个输入。该部件的输出产生其第一和第二输入端接收到的值之和。
2. 减法部件：有两个输入。该部件的输出产生其第一输入端接收到的值与第二输入端接收到的值之差。
3. $k$-移位部件：有一个输入。该部件的输出产生其输入端接收到的值乘以 $2^k$。

在本题中，禁止移位部件从加法或减法部件接收其输入值。求构建所需的 $N$-乘法器电路所需的最少部件数量。

输入格式

输入文件只有一行，包含一个整数 $N$ —— 乘数参数（$2 \le N \le 10^3$）。

输出格式

输出文件应包含一个整数 —— 构建该乘法器所需的最少操作部件数量。

样例

输入样例 1

4

输出样例 1

1

输入样例 2

140

输出样例 2

5

说明

下图展示了两个由 5 个部件组成的乘以 140 的乘法器电路示例。根据题目要求，下方的电路是禁止的（因为移位部件 shift2 接收了来自加法部件 add 的输出 35x）。移位部件、加法部件和减法部件分别用 shift、add 和 sub 表示。