D. Омкар и Война кроватей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Омкар играет в свою любимую видеоигру Война кроватей! В Войне кроватей $$$n$$$ игроков располагаются по кругу, так что для всех $$$j$$$ таких, что $$$2 \leq j \leq n$$$, игрок $$$j - 1$$$ находится слева от игрока $$$j$$$, а игрок $$$j$$$  — справа от игрока $$$j - 1$$$. Кроме того, слева от игрока $$$1$$$ находится игрок $$$n$$$, а справа от игрока $$$n$$$  — игрок $$$1$$$.

В настоящее время каждый игрок атакует либо левого, либо правого игрока. Это означает, что каждого игрока в настоящее время атакует либо $$$0$$$, $$$1$$$ либо $$$2$$$ других игроков. Ключевым элементом стратегии Войны кроватей является то, что если на игрока нападает ровно $$$1$$$ другой игрок, то в ответ он, логически, должен атаковать этого игрока. Если же на игрока нападают либо $$$0$$$ либо $$$2$$$ других игроков, то стратегия Войны кроватей гласит, что игрок может атаковать любого из соседних игроков.

К сожалению, может случиться так, что некоторые игроки в этой игре не следуют правильной стратегии Войны кроватей нужным образом. Омкар знает, на кого в настоящее время нападает каждый игрок, и он может поговорить с любым количеством из $$$n$$$ игроков в игре, чтобы заставить их вместо этого атаковать другого игрока  — то есть, если игрок в настоящее время атаковал игрока слева от него, Омкар может убедить его вместо этого атаковать игрока справа от него; если он в настоящее время атаковал игрока справа от него, Омкар может убедить его вместо этого атаковать игрока слева от него.

Омкар хотел бы, чтобы все игроки действовали логично. Найдите минимальное количество игроков, с которыми Омкар должен поговорить, чтобы после того, как все игроки, с которыми он поговорил (если таковые имеются), изменили игрока, которого они атакуют, все игроки действовали логически в соответствии со стратегией Войны кроватей.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке указано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Ниже приведены описания наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$)  — количество игроков (а значит и кроватей) в этой игре Bed Wars.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длиной $$$n$$$. $$$j$$$-й символ $$$s$$$ равен L, если $$$j$$$-й игрок атакует игрока слева от него, и R, если $$$j$$$-й игрок атакует игрока справа от него.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальное количество игроков, с которыми Омкар должен поговорить, чтобы сделать так, чтобы все игроки действовали логично в соответствии со стратегией Войны кроватей.

Можно доказать, что Омкар всегда может достичь этого при заданных ограничениях.

Пример
Входные данные
5
4
RLRL
6
LRRRRL
8
RLLRRRLL
12
LLLLRRLRRRLL
5
RRRRR
Выходные данные
0
1
1
3
2
Примечание

В первом наборе входных данных игроки $$$1$$$ и $$$2$$$ атакуют друг друга, а игроки $$$3$$$ и $$$4$$$  — друг друга. Каждый игрок атакует ровно $$$1$$$ другого игрока, и каждый игрок атакует игрока, который атакует их, так что все игроки уже действуют логично в соответствии со стратегией Войны кроватей, и Омкару не нужно разговаривать ни с одним из них, следовательно, ответ $$$0$$$.

Во втором наборе входных данных, не каждый игрок действует логически: например, игрока $$$3$$$ атакует только игрок $$$2$$$, но он не атакует его в ответ. Омкару достаточно поговорить с игроком $$$3$$$ для изменения схемы атаки на LRLRRL, в которой все игроки действуют логично в соответствии со стратегией Войны кроватей, делая ответ $$$1$$$.