URI Online Judge | 1709

Shuffled Deck

By Vinícius "Cabessa" Fernandes dos Santos BR Brazil

Timelimit: 1

A card pack has an even number 2n of cards a1 , a2 , . . . , a2n , all distinct (a1 < a2 < · · · < a2n ). The pack is initially sorted, that is, the first card in the pack is a1 , the second is a2 , and so on, and the last card in the pack is a2n.

A handler then performs a shuffling procedure repeatedly. The shuffling consists of two steps:

  1. the pack is divided in the middle;
  2. the cards in the two halves are then interleaved so that if the original sequence at the begining of step 1 is x1, x2,. . . , x2n, then at the end of step 2 the sequence of cards becomes xn+1, x1, xn+2, x2, . . . , x2n, xn.

Given the number of cards in the pack, write a program to determine how many times the shuffling
procedure must be executed so that the pack becomes sorted again.

Input

The input contains several test cases. A test case consists of one line, which contains an even integer P (2P2 x 105 ), where P is the number of cards in the pack (notice that the value P corresponds to the value 2n in the description above).

Output

For each test case in the input your program must produce a single line, containing a single integer, the minimum number of times the shuffling procedure must be executed so that the set becomes sorted again.

Sample Input Sample Output

6

3