#P1175. 山楼粉堞隐悲笳

山楼粉堞隐悲笳

题目描述

叶穿云(字沈墙)楚地秀才,自幼精通算术。

李青琐(字达老)夔州名将,自幼习武。

李将军回乡省亲,在长安买特产带回家的时候不小心看错了价格,无奈只能尽量走水路,与一名叶姓书生同舟共济。

船至白帝城附近,两人听得城上面有胡笳声音传出,以为妙绝,登城拜访。

奏乐者乃一奇女子,她要来者回答出一个问题,否则无法一睹芳容。

女子为郎君准备了 nn 份月饼,第 ii 份的重量为 ii 两。

在制作时候由于贪吃不慎吃去一份(不知道重量是多少了),现在只有 n1n-1 份。

女子将月饼都放在盒子里面,无法打开,而且放入的时候被不慎打乱了。

这是寄托着女子思念的月饼,她可以通过奏乐感应到月饼的灵性。

每次选取一个月饼奏乐,音符为 ii,可以知道对应的重量的二进制表示下面的第 ii 位是不是 00

“我们大唐怎么会知道二进制?”李将军问道。

“妾身认为,周易 2.0 是最好的逻辑系统。”

女子没有那么多时间,她只想知道,自己在最坏的情况下,至少需要吹奏多少次,才知道自己偷吃的月饼的份量(也可以理解为自己至少吹奏多少次保证能找出偷吃的月饼的份量)。

叶书生晃了晃脑袋,脱口而出答案,已经走了。

留下了李将军。

李将军自然是会算的,但是碍于情面,让你出马。

你想被揍扁吗?不想,不想就给我算。

输入格式

输入仅一组数据。

对于每一组数据,第一行输入一个整数 NN2N10000002 \leq N \leq 1\,000\,000),代表有 NN 份月饼。

输出格式

对于每一组数据输出一个数字,表示最少能找到偷吃月饼份量的次数。

样例输入

样例输出