Migrated from Lutece 490 Swap Game

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Last week, children of the kindergarten which Lily attends organized a dinner party to welcome children from their neighborhood kindergarten. Lots of candy and fruit were offered and children all had a good time. What’s more, they played a special game designed by Miss Xue. In this game, children of each kindergarten wore clothes with specific color. The color assigned to clothes for Lily’s kindergarten is red, and for the neighborhood kindergarten is blue.

Children stood in a circle. Adjacent children could swap their place with each other. Miss Xue asked the children to swap so that in the end children of the same kindergarten formed a consecutive sequence.

This game is so funny that everyone was happy. However, Lily wants to know what the minimum number of swaps is needed for children to accomplish the game, given the initial state of the circle. Can you tell her?

Input

First an integer $T$, indicates the number of test cases.

Every test case contains a string which represents the color of clothes children wore at each place. Specifically, $i_{th}$ element of the string is R if the child stood at $i_{th}$ place is from Lily’s kindergarten, B otherwise. Note that the first child is adjacent with the last one. The length of the string is not greater than $100000$.

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and counts from $1$. Then output the minimum number of swaps needed.

Samples

2
RBRBR
BBRBBRBBBRRR

Case #1: 1
Case #2: 5

Resources

Sichuan State Programming Contest 2011