Company: INTEL
Difficulty: medium
The Magician's Deck Lance is a magician, and his signature trick uses a deck of N cards numbered 1 to N from top to bottom. The trick is that Lance keeps shuffling the deck with one fixed technique until every card is back where it started. One shuffle works like this. Lance cuts the deck exactly in the middle into two halves: deck1 holds the top N / 2 cards, in order, deck2 holds the bottom N / 2 cards, in order. He then riffles them back together by taking the 1st card of deck1 , then the 1st card of deck2 , then the 2nd card of deck1 , then the 2nd card of deck2 , and so on, until both halves are exhausted. The result is the new deck, and Lance repeats the whole procedure on it. Given the deck size N , report how many shuffles Lance performs before the deck returns, for the first time, to its original arrangement 1, 2, 3, ..., N . Read the input from STDIN and write the output to STDOUT. Do not print any extra text. Constraints 1 < N < 10000 N is even Input Format A single lin