Deck Shuffling Cycle

You are given a deck of N distinct cards numbered from 1 to N. A perfect out-shuffle is performed by splitting the deck into two halves. The first half contains the first \(\lceil{(N+1)/2}\rceil\) cards and the second half contains the remaining cards. Then, the deck is reassembled by taking cards alternately from the first half and the second half (if available).

Your task is to determine the number of shuffles required to return the deck back to its original order.

Note: When N is odd, the first half has one more card than the second half. The formula for the size of the first half is given by \(\lceil{(N+1)/2}\rceil\).

inputFormat

The input consists of a single integer N denoting the number of cards in the deck. \(1 \leq N \leq 10^5\)

outputFormat

Output a single integer representing the number of shuffles needed to return the deck to its original order.

6

4