题目描述

工厂生产了n个乒乓球。其中有一个乒乓球重量比其他的轻，属于次品，不小心混进了合格品里面。用一个没有砝码的天平可以把次品找出来，方法是：

如果n是偶数，把所有的乒乓球平分成两份，分别放在天平两端，哪边轻次品就在哪边；

如果n是奇数，先随机抽出一个，然后把剩下的平分成两组，分别放在天平两端，哪边轻次品就在哪边；

如果两边一样，那么抽出来的就是次品。

按照这样的方法，继续对有次品的组称重。假如随机抽出来的每一个球，都不是次品，最后一次称重才发现次品，请问总共称重多少次？

输入格式

一个正整数n(1≤n≤10^6)。

输出格式

一个正整数，代表称重总次数。

输入/输出样例

5

2

8

3

说明/提示

时间1000ms，内存256MiB