시간 제한메모리 제한제출정답맞힌 사람정답 비율
서브태스크 참고 (추가 시간 없음) 1024 MB5413866.667%

문제

You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: RedYellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following:

  • Red + Yellow = Orange
  • Red + Blue = Purple
  • Yellow + Blue = Green
  • Red + Yellow + Blue = Gray

You still do not understand shades of colors, therefore the proportion and order of each color in the combination does not matter. For example, combining Red and Yellow produces the same result as combining Yellow and Red, as well as the same result as combining RedYellow, and Red again.

To practice your skills, you want to paint a 1-dimensional painting $P$ of length $N$. Your painting consists of $N$ squares. From left to right, $P_i$ represents the color of the $i-th square. Initially all squares are Uncolored, that is, $P_i$ = Uncolored for every $1≤i≤N$.

In a single stroke, you can choose one of the three primary colors and apply it to a sequence of consecutive squares. In other words, you can choose a color $c$ and two integers $l$ and $r$, such that $1≤l≤r≤N$, and apply color $c$ to all squares $P_j$ such that $l≤j≤r$. If the square being painted is currently Uncolored, then its color will become $c$. Otherwise, the color will be a combination of all the colors applied on this square so far and the new color $c$, as described in the list above.

In order to save time, you want to use as few strokes as possible. Given the description of the painting that you want to paint, figure out what is the minimum number of strokes required to paint it.

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case starts with a line containing an integer $N$, representing the length of the painting. Then on the next line, there will be a string $P$ of length $N$, representing the painting. The $i$-th character represents the color of square $P_i$, according to the following list:

  • U = Uncolored
  • R = Red
  • Y = Yellow
  • B = Blue
  • O = Orange
  • P = Purple
  • G = Green
  • A = Gray

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of strokes required to paint the painting.

제한

  • $1≤T≤100$.
  • $1≤N≤10^5$.

Test Set 1 (9점)

시간 제한: 20 초

  • $P_i$ will be one of {Y, B, G}.

Test Set 2 (11점)

시간 제한: 40 초

  • $P_i$ will be one of {U, R, Y, B, O, P, G, A}.

예제 입력 1

2
9
YYYBBBYYY
6
YYGGBB

예제 출력 1

Case #1: 3
Case #2: 2

In Sample Case #1, the solution is to make $3$ strokes: the first one using color Yellow from square $1$ through $3$, the second one using color Blue from square $4$ through $6$, and the third one using color Yellow from square $7$ through $9$. Notice that this particular painting required only primary colors.

In Sample Case #2, the solution is to make $2$ strokes: the first one using color Yellow from square $1$ through $4$, and the second one using color Blue from square $3$ through $6$. Notice that squares $3$ and $4$ will be painted with both colors Yellow and Blue, which will result on it being Green.

예제 입력 2

1
5
ROAOR

예제 출력 2

Case #1: 3

In Sample Case #3, the solution is to make $3$ strokes: the first one using color Red from square $1$ through $5$, the second one using color Yellow from square $2$ through $4$, and the third one using color Blue on square $3$. Notice that square $3$ is painted with all three primary colors, which will result in it being Gray.

채점 및 기타 정보

  • 예제는 채점하지 않는다.