CF1392D.Omkar and Bed Wars

Omkar is playing his favorite pixelated video game, Bed Wars! In Bed Wars, there are $n$ players arranged in a circle, so that for all $j$ such that $2 \leq j \leq n$, player $j - 1$ is to the left of the player $j$, and player $j$ is to the right of player $j - 1$. Additionally, player $n$ is to the left of player $1$, and player $1$ is to the right of player $n$.

Currently, each player is attacking either the player to their left or the player to their right. This means that each player is currently being attacked by either $0$, $1$, or $2$ other players. A key element of Bed Wars strategy is that if a player is being attacked by exactly $1$ other player, then they should logically attack that player in response. If instead a player is being attacked by $0$ or $2$ other players, then Bed Wars strategy says that the player can logically attack either of the adjacent players.

Unfortunately, it might be that some players in this game are not following Bed Wars strategy correctly. Omkar is aware of whom each player is currently attacking, and he can talk to any amount of the $n$ players in the game to make them instead attack another player — i. e. if they are currently attacking the player to their left, Omkar can convince them to instead attack the player to their right; if they are currently attacking the player to their right, Omkar can convince them to instead attack the player to their left.

Omkar would like all players to be acting logically. Calculate the minimum amount of players that Omkar needs to talk to so that after all players he talked to (if any) have changed which player they are attacking, all players are acting logically according to Bed Wars strategy.

Omkar 正在玩他最喜爱的像素风电子游戏《床战》（Bed Wars）！在《床战》中，共有 $n$ 名玩家围成一个圆圈排列：对所有满足 $2 \leq j \leq n$ 的 $j$，玩家 $j-1$ 位于玩家 $j$ 的左侧，而玩家 $j$ 位于玩家 $j-1$ 的右侧。此外，玩家 $n$ 位于玩家 $1$ 的左侧，玩家 $1$ 位于玩家 $n$ 的右侧。

目前，每名玩家正在攻击其左侧或右侧的玩家之一。因此，每名玩家当前正受到 $0$、$1$ 或 $2$ 名其他玩家的攻击。《床战》策略的一个关键原则是：若某玩家恰好受到 $1$ 名其他玩家的攻击，则该玩家理应回击那名攻击者；而若某玩家受到 $0$ 名或 $2$ 名其他玩家的攻击，则根据《床战》策略，该玩家可逻辑地选择攻击其任意一名相邻玩家（左或右均可）。

不幸的是，当前游戏中可能有部分玩家并未正确遵循《床战》策略。Omkar 已知每名玩家当前正在攻击谁，并且他可以与任意数量的 $n$ 名玩家交谈，说服他们改为攻击另一侧的玩家——即：若某玩家当前正在攻击其左侧玩家，Omkar 可说服其改为攻击其右侧玩家；若其当前正在攻击其右侧玩家，Omkar 可说服其改为攻击其左侧玩家。

Omkar 希望所有玩家均按《床战》策略合理行动。请计算 Omkar 所需交谈的最少玩家人数，使得在他所交谈的所有玩家（如有）均更改其攻击目标后，所有玩家均符合《床战》策略。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The descriptions of the test cases follows.

The first line of each test case contains one integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the amount of players (and therefore beds) in this game of Bed Wars.

The second line of each test case contains a string $s$ of length $n$. The $j$-th character of $s$ is equal to L if the $j$-th player is attacking the player to their left, and R if the $j$-th player is attacking the player to their right.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$）—— 表示“床战”游戏中玩家（即床铺）的数量。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。字符串 $s$ 的第 $j$ 个字符为 L，表示第 $j$ 位玩家正在攻击其左侧的玩家；为 R，则表示第 $j$ 位玩家正在攻击其右侧的玩家。

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

For each test case, output one integer: the minimum number of players Omkar needs to talk to to make it so that all players are acting logically according to Bed Wars strategy.

It can be proven that it is always possible for Omkar to achieve this under the given constraints.

对于每个测试用例，输出一个整数：Omkar 需要交谈的最少玩家数量，使得所有玩家均按照 Bed Wars 策略进行逻辑行动。

在给定约束条件下，可以证明 Omkar 总是能够实现这一目标。

In the first test case, players $1$ and $2$ are attacking each other, and players $3$ and $4$ are attacking each other. Each player is being attacked by exactly $1$ other player, and each player is attacking the player that is attacking them, so all players are already being logical according to Bed Wars strategy and Omkar does not need to talk to any of them, making the answer $0$.

In the second test case, not every player acts logically: for example, player $3$ is attacked only by player $2$, but doesn't attack him in response. Omkar can talk to player $3$ to convert the attack arrangement to LRLRRL, in which you can see that all players are being logical according to Bed Wars strategy, making the answer $1$.

在第一个测试用例中，玩家 $1$ 和 $2$ 互相攻击，玩家 $3$ 和 $4$ 也互相攻击。每位玩家恰好被另外一名玩家攻击，且每位玩家都攻击正在攻击自己的那名玩家，因此所有玩家均已符合 Bed Wars 策略的逻辑性，Omkar 无需与任何玩家交谈，答案为 $0$。

在第二个测试用例中，并非所有玩家都行为合乎逻辑：例如，玩家 $3$ 仅受到玩家 $2$ 的攻击，却未反击玩家 $2$。Omkar 可以与玩家 $3$ 交谈，将攻击模式调整为 LRLRRL；在此模式下，可见所有玩家均符合 Bed Wars 策略的逻辑性，因此答案为 $1$。