bee 1709 - Shuffled Deck

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

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

the pack is divided in the middle;
the cards in the two halves are then interleaved so that if the original sequence at the begining of step 1 is x₁, x₂,. . . , x_2n, then at the end of step 2 the sequence of cards becomes x_n+1, x₁, x_n+2, x₂, . . . , x_2n, x_n.

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 (2 ≤ P ≤ 2 x 10⁵ ), 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