22842_CowShuffle

Each time cows shuffle a deck of 2N (1 ≤ N ≤ 9,000) cards marked 1..2N they do it as follows:

* Cut the deck exactly in half to form two piles (A and B) of N cards each. A is the top N cards and B is the bottom N cards.

* Combine the cards back together into a single pile by taking one card from pile A and placing it face down on a new pile and then one card from pile B and placing it face down on top of the first card, then one from A and one from B and so on until all the cards are perfectly shuffled back into a single pile.

They repeat this cow shuffle again and again until the cards are back in their original order.

Given N, how many cow shuffles does it take to return the cards to their original order?

EXAMPLE:

Let N be 3; therefore, the the cards are {1, 2, 3, 4, 5, 6} and the shuffles go like this:

orig   shuf1  shuf2   shuf3  shuf4
 1      6      1      6      1
 2      3      5      4      2
 3   -> 5   -> 4   -> 2   -> 3
 4      2      3      5      4
 5      4      2      3      5
 6      1      6      1      6

So, four cow shuffles suffice to put the deck of three cards back in order.

A single line with the integer N

A single line with the integer number of shuffles required to return 2N cards to their original order.

3

4