暂无测试数据。

Description

FJ 设计了一台简单的计算机，只有两个寄存器。FJ 希望用它算出整数的 \(P(1 \le P \le 20,000)\)次幂。一开始，两个寄存器的数值分别为底数 \(X\) 和 \(1\)。计算机支持的运算包括相乘和相除，每次从两个寄存器中各取一个数字进行运算，或者从同一个寄存器中读取同一个数字两次进行运算。运算结果必须保存在某一个寄存器内。所有运算结果必须是整数。

比如，如果想计算 \(x^{31}\)，一种计算方法是：

因此 \(x^{31}\)可以通过 6 次计算得出。
给出需要计算的幂次，求出最少需要几次计算。

Format

Input

仅一个整数 \(P\)。

Output

仅一个整数，表示最少计算次数。

Sample 1

Input

31

Output

6

Limitation

1s, 256MiB for each test case.

Source

东莞中学暑假测试题（1）