Shuffling Along

Most of you have played card games (and if you haven’t, why not???) in which the deck of cards is randomized by shuffling it one or more times.

A *perfect shuffle * is a type of shuffle where the
initial deck is divided exactly in half, and the two halves are
perfectly interleaved. For example, a deck consisting of eight
cards ABCDEFGH (where A is the top card of the deck) would be
divided into two halves ABCD and EFGH and then interleaved to
get AEBFCGDH. Note that in this shuffle the original top card
(A) stays on top — this type of perfect shuffle is called an
*out-shuffle*. An equally valid perfect shuffle would
start with the first card from the second half and result in
EAFBGCHD — this is known as an *in-shuffle*.

While normal shuffling does a good job at randomizing a deck, perfect shuffles result in only a small number of possible orderings. For example, if we perform multiple out-shuffles on the deck above, we obtain the following:

So after 3 out-shuffles, the deck is returned to its original state. A similar thing happens if we perform multiple in-shuffles on an 8-card deck, though in this case it would take 6 shuffles before we get back to where we started. With a standard 52 card deck, only 8 out-shuffles are needed before the deck is returned to its original order (talented magicians can make use of this result in many of their tricks). These shuffles can also be used on decks with an odd number of cards, but we have to be a little careful: for out-shuffles, the first half of the deck must have 1 more card than the second half; for in-shuffles, it’s the exact opposite. For example, an out-shuffle on the deck ABCDE results in ADBEC, while an in-shuffle results in CADBE.

For this problem you will be given the size of a deck and must determine how many in- or out-shuffles it takes to return the deck to its pre-shuffled order.

The input consists of one line containing a positive integer
$n \leq 1000$ (the size of
the deck) followed by either the word `in` or
`out`, indicating whether you should perform
in-shuffles or out-shuffles.

For each test case, output the case number followed by the number of in- or out-shuffles required to return the deck to its original order.

Sample Input 1 | Sample Output 1 |
---|---|

8 out |
3 |

Sample Input 2 | Sample Output 2 |
---|---|

8 in |
6 |

Sample Input 3 | Sample Output 3 |
---|---|

52 out |
8 |

Sample Input 4 | Sample Output 4 |
---|---|

53 out |
52 |