众所周知，xry111在硬件方面非常矬，修个耳机都能把声道焊反。现在，xry111为了传送iPhone输出的n声道音频，要接一根n声道音频线。这种线中有n根信号线和1根地线，其中地线以屏蔽层的形式出现，很好区分。但是，对于n根信号线，xry111感觉十分头疼，不敢随意连接，只好拿万用表的导通测试档测定两端线头的对应关系。

例如，若n=3，xry111要确定A端的某根线头与B端的哪一根线头相连，他就把万用表红表笔接在这根线头上，黑表笔逐个测试B端的3根线头。当万用表发出响声时，就说明此时黑表笔与红表笔连接同一根线。

显然，用这种方法，最坏情况下，他要测试n次才能找到B端对应的线头。

但是，xry111发现，他并不需要测量这么多次。例如，n=5时，xry111将B端的线头编号为1～5，则他可以把红表笔接在A端的待测线头，然后把B端的线头2、4一起接黑表笔测量一次，线头3、4一起测量一次，再单独测量一次线头5。测量结果可能有：
（1）第1次响，第2、3次不响，结果是线头2。
（2）第1、2次响，第3次不响，结果是线头4。
（3）第1次不响，第2次响，第3次不响，结果是线头3。
（4）第1、2次不响，第3次响，结果是线头5。
（5）3次都不响，结果是线头1。

现在，xry111想知道，在n确定的情况下，他最坏情况下要测量多少次，才能确定A端某根线对应在B端的线。你可以认为，音频线没有损坏，即A端的每根线头与且仅与B端的1根线头相连。

输入包含多组数据，请处理到EOF。
每组数据包括1行，仅包含一个整数n。
对于100%的数据，有1<=n<=10¹⁸。
输入文件满足数据组数小于等于10000。

对于每组输入，输出1行，包含一个整数，表示xry111在最坏情况下的测量次数。

第2组样例输入就是问题描述中的那个例子。

XDUACM 2014暑期集训第7场