P16866 [GKS 2021 #H] Painter

You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: Red, Yellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following: - $\text{Red} + \text{Yellow} = \text{Orange}$ - $\text{Red} + \text{Blue} = \text{Purple}$ - $\text{Yellow} + \text{Blue} = \text{Green}$ - $\text{Red} + \text{Yellow} + \text{Blue} = \text{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 Red, Yellow, 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 = \text{Uncolored}$ for every $1 \le i \le 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 \le l \le r \le N$, and apply color $c$ to all squares $P_j$ such that $l \le j \le 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 = \text{Uncolored}$ - $R = \text{Red}$ - $Y = \text{Yellow}$ - $B = \text{Blue}$ - $O = \text{Orange}$ - $P = \text{Purple}$ - $G = \text{Green}$ - $A = \text{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.

### Limits $1 \le T \le 100$. $1 \le N \le 10^5$. **Test Set $1$** $P_i$ will be one of $\{Y, B, G\}$. **Test Set $2$** $P_i$ will be one of $\{U, R, Y, B, O, P, G, A\}$.