Shuffled Deck

Time limit2sMemory limit512 MB

Summary

For a deck of P distinct cards, find how many times the given interleaving shuffle must be repeated until the deck returns to its sorted order.

Level: Medium5 of 10
Topics: Math, Sorting, Number theory
Solved: No attempts yet

Problem

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.

Split the deck into two halves.
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.

Input

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.

Output

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

Examples4

Example 1
Input
```
4
```
Expected output
```
4
```
Example 2
Input
```
6
```
Expected output
```
3
```
Example 3
Input
```
2
```
Expected output
```
2
```
Example 4
Input
```
100002
```
Expected output
```
100002
```