← 返回题目列表

Codeforces · 1392/D

D. 奥姆卡和床战争

中文机器翻译题面 查看原题

Omkar 正在玩他最喜欢的像素化视频游戏 Bed Wars!在 Bed Wars 中,有 $$$n$$$ 玩家排列成一个圆圈,因此对于所有 $$$j$$$,使得 $$$2 \leq j \leq n$$$,玩家 $$$j - 1$$$ 位于玩家 $$$j$$$ 的左侧,玩家 $$$j$$$ 位于玩家 $$$j - 1$$$ 的右侧。此外,玩家 $$$n$$$ 位于玩家 $$$1$$$ 的左侧,玩家 $$$1$$$ 位于玩家 $$$n$$$ 的右侧。

目前,每个玩家正在攻击他们左边的玩家或右边的玩家。这意味着每个玩家当前都受到 $$$0$$$、$$$1$$$ 或 $$$2$$$ 其他玩家的攻击。 Bed Wars 策略的一个关键要素是,如果一名玩家正受到 $$$1$$$ 其他玩家的攻击,那么他们应该按逻辑攻击该玩家作为回应。相反,如果玩家受到 $$$0$$$ 或 $$$2$$$ 其他玩家的攻击,则床战策略表明该玩家可以逻辑上攻击相邻玩家中的任何一个。

不幸的是,这款游戏中的某些玩家可能没有正确遵循床战策略。 Omkar 知道每个玩家当前正在攻击谁,他可以与游戏中任意数量的 $$$n$$$ 玩家交谈,让他们攻击另一个玩家 - 即。 e.如果他们当前正在攻击左边的玩家,奥姆卡可以说服他们转而攻击右边的玩家;如果他们当前正在攻击右侧的玩家,奥姆卡可以说服他们攻击左侧的玩家。

Omkar 希望所有玩家都能按逻辑行事。计算 Omkar 需要与之交谈的最少玩家数量,以便在与他交谈的所有玩家(如果有)都改变了他们正在攻击的玩家后,所有玩家都按照 Bed Wars 策略逻辑行动。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 此 Bed Wars 游戏中的玩家数量(以及床位)。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$。如果第 $$$j$$$ 个玩家攻击其左侧的玩家,则 $$$s$$$ 的第 $$$j$$$ 个字符等于 L;如果第 $$$j$$$ 个玩家攻击其右侧的玩家,则等于 R。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:Omkar 需要与之交谈的最少玩家数量,以便所有玩家都根据 Bed Wars 策略逻辑地行动。

可以证明,在给定的约束下,Omkar 总是有可能实现这一目标。

示例

输入 #1

5
4
RLRL
6
LRRRRL
8
RLLRRRLL
12
LLLLRRLRRRLL
5
RRRRR

输出 #1

0
1
1
3
2

注意

在第一个测试用例中,玩家 $$$1$$$ 和 $$$2$$$ 互相攻击,玩家 $$$3$$$ 和 $$$4$$$ 互相攻击。每个玩家都受到 $$$1$$$ 其他玩家的攻击,并且每个玩家都在攻击正在攻击他们的玩家,因此根据 Bed Wars 策略,所有玩家都已经符合逻辑,Omkar 不需要与他们中的任何一个交谈,得出答案 $$$0$$$。

在第二个测试用例中,并非每个玩家都按逻辑行事:例如,玩家 $$$3$$$ 仅受到玩家 $$$2$$$ 的攻击,但不会攻击他作为回应。 Omkar可以与玩家$$$3$$$交谈,将攻击安排转换为LRLRRL,其中可以看到所有玩家都按照Bed Wars策略进行逻辑推理,得出答案$$$1$$$。