P16866 [GKS 2021 #H] Painter

你最近开始学习绘画，在最初的一节课上你学到了三种原色：红色、黄色和蓝色。如果你将这些颜色混合，可以产生更多颜色。目前，你已经学到的混合规则如下： - 红色 + 黄色 = 橙色 - 红色 + 蓝色 = 紫色 - 黄色 + 蓝色 = 绿色 - 红色 + 黄色 + 蓝色 = 灰色 你还不理解颜色的深浅，因此混合中每种颜色的比例和顺序并不重要。例如，混合红色和黄色与混合黄色和红色得到的结果相同，也与再次混合红色、黄色和红色得到的结果相同。 为了练习技能，你想绘制一幅长度为 $N$ 的一维画作 $P$。画作由 $N$ 个方格组成。从左到右，$P_i$ 表示第 $i$ 个方格的颜色。初始时所有方格都是未涂色的，即对于 $1 \le i \le N$，$P_i = \text{Uncolored}$。 在一次笔划中，你可以选择三种原色之一，并将其应用到一段连续的方格序列上。换句话说，你可以选择一个颜色 $c$ 和两个整数 $l$、$r$，满足 $1 \le l \le r \le N$，然后将颜色 $c$ 应用到所有满足 $l \le j \le r$ 的方格 $P_j$ 上。如果当前被涂色的方格是未涂色的，那么它的颜色将变为 $c$。否则，该方格的颜色将变为到目前为止应用在此方格上的所有颜色与新的颜色 $c$ 的混合结果，混合规则如上所述。 为了节省时间，你希望使用尽可能少的笔划。根据你想要绘制的画作的描述，找出绘制它所需的最少笔划数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$，表示画作的长度。下一行包含一个长度为 $N$ 的字符串 $P$，表示画作。第 $i$ 个字符表示方格 $P_i$ 的颜色，对应关系如下： - `U` = 未涂色 - `R` = 红色 - `Y` = 黄色 - `B` = 蓝色 - `O` = 橙色 - `P` = 紫色 - `G` = 绿色 - `A` = 灰色

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是绘制画作所需的最少笔划数。

### 限制条件 $1 \le T \le 100$。 $1 \le N \le 10^5$。 **测试集 1** $P_i$ 将是 $\{Y, B, G\}$ 之一。 **测试集 2** $P_i$ 将是 $\{U, R, Y, B, O, P, G, A\}$ 之一。 翻译由 DeepSeek V4 Pro 完成