The proud Breton that you are really fancies surfing on Britanny's coastlines. As you want to share your favorite hobbies with all of your new friends, you bought a gigantic surfboard, so that all of your \(n\) friends can fit. Eager as you are to test it, you did not realize that there is nothing on the board that beginners can grip to prevent themselves from falling. As soon as the first wave hits, everybody clings to one side of the board, creating a major imbalance.

Thinking quickly, you remember that you packed a saw in your swimming trunks. After a quick calculation, you realize that the only way to prevent the board from sinking is to cut it in three parts. The front and back parts will sink, and you will lose the friends you had there forever. You will stay in the middle part, which has to be well-balanced. To achieve this, the number of people on the left side of the board has to be the same as the number of people on the right side. The people that you thus saved will remain your friends (for now). Before cutting the board, you try to quickly calculate how many friends you will have left, at most.

Input

On the first line, an integer \(1 \leq N \leq 10\), that indicates the number of test cases. For each test case, on the first line, \(1 \leq n \leq 10^6\), that indicates the number of friends that you have in this test case. On the following \(n\) lines, line \(i\) contains either L or R, which indicates whether friend \(i\) leans on the left or the right side of the board.

Output

For each test case, your program has to output one line. For test case \(i\), if the most friends you can have is \(l\), output Case i: l

Sample Input

2
5
R
R
L
R
R
3
L
L
L

Sample Output

Case 1: 2
Case 2: 0