Shuffled Deck

A deck holds an even number $2n$ of cards $a_1, a_2, \dots, a_{2n}$, all distinct ($a_1 < a_2 < \dots < a_{2n}$). At the start the deck is perfectly sorted: the first card is $a_1$, the second card is $a_2$, and so on until the last card, which is $a_{2n}$.

A dealer then repeats a shuffle made of two steps.

1. Split the deck into two halves.
2. Interleave the cards of the two halves. If the card order at the start of step 1 is $x_1, x_2, \dots, x_{2n}$, then after step 2 the order becomes $x_{n+1}, x_1, x_{n+2}, x_2, \dots, x_{2n}, x_n$.

Given the number of cards in the deck, write a program that determines how many times this shuffle must be repeated for the deck to return to its original sorted order.

The first line contains an even integer $P$, the number of cards in the deck ($2 \le P \le 2 \times 10^5$). The value $P$ corresponds to $2n$ in the description above.

Print one line with a single integer, the minimum number of times the shuffle must be repeated for the deck to be sorted again.