Омкар играет в свою любимую видеоигру Война кроватей! В Войне кроватей \(n\) игроков располагаются по кругу, так что для всех \(j\) таких, что \(2 \leq j \leq n\), игрок \(j - 1\) находится слева от игрока \(j\), а игрок \(j\) — справа от игрока \(j - 1\). Кроме того, слева от игрока \(1\) находится игрок \(n\), а справа от игрока \(n\) — игрок \(1\).
В настоящее время каждый игрок атакует либо левого, либо правого игрока. Это означает, что каждого игрока в настоящее время атакует либо \(0\), \(1\) либо \(2\) других игроков. Ключевым элементом стратегии Войны кроватей является то, что если на игрока нападает ровно \(1\) другой игрок, то в ответ он, логически, должен атаковать этого игрока. Если же на игрока нападают либо \(0\) либо \(2\) других игроков, то стратегия Войны кроватей гласит, что игрок может атаковать любого из соседних игроков.
К сожалению, может случиться так, что некоторые игроки в этой игре не следуют правильной стратегии Войны кроватей нужным образом. Омкар знает, на кого в настоящее время нападает каждый игрок, и он может поговорить с любым количеством из \(n\) игроков в игре, чтобы заставить их вместо этого атаковать другого игрока — то есть, если игрок в настоящее время атаковал игрока слева от него, Омкар может убедить его вместо этого атаковать игрока справа от него; если он в настоящее время атаковал игрока справа от него, Омкар может убедить его вместо этого атаковать игрока слева от него.
Омкар хотел бы, чтобы все игроки действовали логично. Найдите минимальное количество игроков, с которыми Омкар должен поговорить, чтобы после того, как все игроки, с которыми он поговорил (если таковые имеются), изменили игрока, которого они атакуют, все игроки действовали логически в соответствии со стратегией Войны кроватей.
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество игроков, с которыми Омкар должен поговорить, чтобы сделать так, чтобы все игроки действовали логично в соответствии со стратегией Войны кроватей.
Можно доказать, что Омкар всегда может достичь этого при заданных ограничениях.
Примечание
В первом наборе входных данных игроки \(1\) и \(2\) атакуют друг друга, а игроки \(3\) и \(4\) — друг друга. Каждый игрок атакует ровно \(1\) другого игрока, и каждый игрок атакует игрока, который атакует их, так что все игроки уже действуют логично в соответствии со стратегией Войны кроватей, и Омкару не нужно разговаривать ни с одним из них, следовательно, ответ \(0\).
Во втором наборе входных данных, не каждый игрок действует логически: например, игрока \(3\) атакует только игрок \(2\), но он не атакует его в ответ. Омкару достаточно поговорить с игроком \(3\) для изменения схемы атаки на LRLRRL, в которой все игроки действуют логично в соответствии со стратегией Войны кроватей, делая ответ \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
RLRL
6
LRRRRL
8
RLLRRRLL
12
LLLLRRLRRRLL
5
RRRRR
|
0
1
1
3
2
|