Description
Suppose that we have a deck of n(= 2*k) cards, labeled by 1 to n from top to bottom(Like fig.1). A perfect shuffle is a process that divides the cards into equal-sized parts, one with the top k cards, and the other with bottom k cards,, and then re-arranges the card so that the cards of two parts interleave each other; Precisely, the order after a perfect shuffle becomes {k+1, 1, k+2, 2, ..., n, k}(Like fig.2)
We may perform the same shuffling process again and again, so that the order of the cards resumes 1, 2, 3, ..., n.
For example, if n is 4, after the first shuffle we have:
3, 1, 4, 2 (Like fig.3)
Do it again, and the order becomes:
4, 3, 2, 1 (Like fig.4)
The third shuffle yields:
2, 4, 1, 3 (Like fig.5)
And finally, it goes back to:
1, 2, 3, 4 (Like fig.6)
In this question, we are given n as the input, and ask for the minimum number of shuffles (>= 1) to resume the original order.
E.g., n = 2, min num of shuffles = 2.
n = 4, min num of shuffles = 4.
n = 6, min num of shuffles = 3.
Input
The input consists of multiple lines. Each line is a test case, containing a integer n(0 < n <= 1000).
Case 1: n is not more than 10.
Case 2: n is not more than 100.
Case 3: n is not more than 500.
Case 4: n is not more than 1000.
Output
For each case, output the minimum number of shuffles.