Taco Painting

In this problem, you are given a string of length N consisting of characters 'R' and 'B'. These characters represent posts painted in red (R) and blue (B), respectively. You are allowed to repaint some of the red posts to blue. Your task is to determine the minimum number of consecutive segments of posts having the same color after performing an optimal repainting operation.


Explanation:
Consider the string RBBRBRR which can be divided initially into 5 segments: R, BB, R, B, RR. By repainting appropriate posts, the minimum sections you can obtain is 3. Formally, if the original number of sections is S, the answer will be (\lceil S/2 \rceil) or equivalently (\frac{S+1}{2}) (integer division) since you can repaint to merge adjacent sections optimally.

inputFormat

The first line of the input contains an integer T, the number of test cases. For each test case, the first line contains an integer N, representing the number of posts. The second line contains a string of length N consisting only of characters 'R' and 'B'.

outputFormat

For each test case, output a line in the format: "Case #i: X", where i is the test case number (starting from 1) and X is the minimum number of consecutive segments after repainting.## sample

4
7
RBBRBRR
5
RRRRR
8
BBBRRBBR
8
RRBRBBBR

Case #1: 3
Case #2: 1
Case #3: 2
Case #4: 3