Card Shuffling Order

There are \(2n\) cards numbered from \(1,2,3,\dots,n,n+1,\dots,2n\). This is also the initial order of the cards. One shuffle rearranges the cards into the following order:

\(n+1,\; 1,\; n+2,\; 2,\; n+3,\; 3,\; \dots,\; 2n,\; n\)

It can be proven that for any natural number \(n\), after some number \(m\) of shuffles the deck returns to its initial order for the first time. Given \(n\) (with \(n \le 10^8\)), compute the value of \(m\).

Hint: The answer \(m\) is the order of \(2\) modulo \(2n+1\); in other words, \(m\) is the smallest positive integer such that

\(2^m \equiv 1 \pmod{2n+1}\).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^8\)).

outputFormat

Output the minimum number \(m\) such that after \(m\) shuffles the deck returns to its original order.

sample

1

2