U694089 [26CCFCAT-F] 奇怪染料
题目描述
某实验室研制出了一种特殊染料，只有三种基础颜色：
* `R`（红色）
* `G`（绿色）
* `B`（蓝色）
这些染料具有特殊性质：
* 如果一个位置为空白（记为 `N`），刷上颜色 $c$，则变为 $c$；
* 如果一个位置已经是颜色 $c$，再刷一次颜色 $c$，则颜色不会发生变化；
* 如果一个位置已经是另一种颜色，则会与新颜色发生反应，变成第三种颜色。
具体反应规则如下表：
|原颜色|新颜色|结果|
|------|-------|-----|
|R|G|B|
|G|R|B|
|G|B|R|
|B|G|R|
|B|R|G|
|R|B|G|
给定一个长度为 $n$ 的目标序列，由`R`、`G`、`B`三种颜色以及空白（`N`）组成。
初始时，你有一个长度同样为 $n$ 的初始序列，所有位置均为空白（`N`）。
每次操作，你可以选定一个连续区间 $[l,r]$ 和一种颜色 $c\in${`R`，`G`，`B`}，随后将区间内的所有位置同时刷上颜色 $c$。
请你计算将初始序列变成目标序列所需的最少操作次数。
输入格式
**本题的输入包含多组测试用例。**
第一行一个整数 $T（1\le T \le 1000）$，表示测试用例的数量。对于每组测试用例：
* 第一行一个整数 $n(1 \le n \le 2 \times 10^5)$，表示序列长度；
* 第二行一个长度为 $n$ 的字符串 $s$，表示目标序列。字符串仅包含字符`R`、`G`、`B`、`N`。
保证所有测试用例的 $n$ 的总和不超过 $2 \times 10^5$。
输出格式
对于每组测试用例：输出一行一个整数，表示最少操作次数。
说明/提示
对于第一组测试用例，依次进行三次操作即可：
可以证明，无法在 $2$ 次操作内完成，故最少操作次数为 $3$。