洗牌游戏

Time Limit: 2000MS

Memory Limit: 131072KB

Description


Lich同学特别喜欢打牌,打牌中难免需要洗牌,洗着洗着,Lich从中悟出了一种新的洗牌方式。简单来说,有2n张不同的牌,放在1~2n个有序的位置上,初始情况下,牌放的序列为:1,2,3...2*n,并且洗牌规则如下:第i张牌会被洗到p(i)张牌上,并且:

p(i) = 2i   当i<=n

p(i) = 2(i - n) - 1 当i>n

Lich现在很想知道,当洗牌重新洗回到序列:1,2,3...2*n,对于每一个n,自己需要洗牌的最少次数是多少?



Input

对于每组样例,输入一行n,1<= n <= 2^31-1。

Output

最少洗牌次数

Sample Input

1

Sample Output

2

Hint

None

Source

None

提交代码