Shuffled Deck

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 be- gining 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 (2 ≤ P ≤ 2 × 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 4 6 2 100002 Sample Output 4 3 2 100002