SP275 WATERWAY - The Water Ringroad

在一个遥远的地方，整个居民都居住在山顶上的城池，而这些城池围绕着一个被称为「圆圈」的高原。城市的高级议员们设计了一个复杂的通信系统：城市之间通过一个圆形水道相连。这条水道环绕所有城市，可以将塞有讯息的小纸船放在水道里，由一个小锡兵驾驶，纸船会按既定路径，顺次从一个城市漂流到下一个，直到目标城市。然而，由于一些水道段只能单向通行（因为有瀑布），因此某些城市之间可能无法通信。 随着时间推移，这一系统的弊端愈发突出。水道狭窄，使得两艘对向航行的小船无法会车。而且，某些城市为了提高速度，将小锡兵换成了塑料士兵。这使得速度较快的船只必须排在慢速船的后面，导致大家怨声载道。议员们为了解决问题，提出在每一对可以通信的城市 A 和 B 之间建造两条独立的通道：一条负责从 A 到 B，另一条负责从 B 到 A（如果在旧水道中某个方向上无法通信，新的水道中也无需启用该方向的通信）。 然而，圆圈的高级祭司们提出了反对意见。他们坚决认为，任何新建的水道应保持圆形，必须环绕所有城市，就像原来的水道那样。而且，船只的航线必须保持为两个相邻城市之间的完整弧度。因此，新的通道实际上应该由一系列相邻的圆弧组成，而且任何两条通道不能共用一个弧线。 工程师们指出，新的圆弧系统在瀑布段上会面临与旧水道一样的问题。考虑到这一点，给定旧水道的地图，需要计算新水道最少需要多少条独立的圆弧路径。

输入以一个整数 $t \leq 100$ 开始，表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例包括两行。第一行是一个整数 $n$（$3 \leq n \leq 100000$），代表圆圈上的城市数量。第二行是一个长度为 $n$ 的字符串，由字符 'A'、'B' 或 'C' 组成（中间没有空格），表示城市之间的弧线状态，这些字符依次表示城市 1-2、2-3、...、$n-1$-$n$、和 $n$-1，并且意义如下：'A' - 弧线只允许逆时针通行，'B' - 弧线允许双向通行，'C' - 弧线只允许顺时针通行。

对于每个测试用例，输出一行，包含一个整数 —— 新水道所需的最小圆弧数。 **本翻译由 AI 自动生成**