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.


-----Input-----

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$.


-----Output-----

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.


-----Example-----
Input
5
4
RLRL
6
LRRRRL
8
RLLRRRLL
12
LLLLRRLRRRLL
5
RRRRR

Output
0
1
1
3
2



-----Note-----

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$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    s = input().strip()

    lengths = []
    curr = s[0]
    currLen = 0
    for c in s:
        if c == curr:
            currLen += 1
        else:
            lengths.append(currLen)
            currLen = 1
            curr = c
    if currLen < n and s[0] == s[-1]:
        lengths[0] += currLen
    else:
        lengths.append(currLen)


    out = 0
    if len(lengths) == 1 and n >= 3:
        out = 1
        lengths[0] -= 1
        lengths.append(1)
        

    for v in lengths:
        out += v // 3
    print(out)
    


def ne(c):
    if c == 'L':
        return 'R'
    return 'L'

# for _ in range(1):
for _ in range(int(input())):
    # n, k = map(int, input().split())
    n = int(input())
    s = input()
    ans = 0
    if s[0] * n == s:
        ans += 1
        s = ne(s[0]) + s[0] * (n - 1)
    if s[0] == s[-1]:
        i = 0
        while s[i] == s[0]:
            i += 1
        s = s[i:] + s[:i]
    lst = '#'
    cnt = 0
    for i in range(n):
        if lst != s[i]:
            lst = s[i]
            ans += cnt // 3
            cnt = 1
        else:
            cnt += 1
    ans += cnt // 3
    print(ans)


import sys
input = lambda: sys.stdin.readline().rstrip()
T = int(input())
for _ in range(T):
    N = int(input())
    S = input()
    X = []
    prev = S[0]
    c = 0
    for i, s in enumerate(S):
        if s == prev:
            c += 1
        else:
            X.append(c)
            prev = s
            c = 1
    if not X:
        X.append(N + 2)
    elif prev == S[0]:
        X[0] += c
    else:
        X.append(c)
    print(sum([x // 3 for x in X]))



for _ in range(int(input())):
    x = int(input())
    s = input()
    if 'R' in s and "L" in s:
        A = []
        if s[0] == 'R':
            A.append([1, 1])
        else:
            A.append([2, 1])
        for i in range(1, len(s)):
            if A[-1][0] == 1:
                if s[i] == 'R':
                    A[-1][1] += 1
                else:
                    A.append([2, 1])
            else:
                if s[i] == 'L':
                    A[-1][1] += 1
                else:
                    A.append([1, 1])
        if A[0][0] == A[-1][0]:
            A[0][1] += A[-1][1]
            A.pop()
        Ans = 0
        for i in range(len(A)):
            Ans += A[i][1] // 3
        print(Ans)
    else:
        print((len(s) + 2) // 3)

def solve():
    n = int(input())
    lst = list(input())
    if len(set(lst)) == 1:
        print(n//3 + ((n%3) != 0))
        return 0

    for i in range(n - 1):
        if lst[i] != lst[i + 1]:
            q = i + 1
            break
    lst = [lst[i] for i in range(q, n)] + [lst[i] for i in range(q)]
    rcnt = 0
    lcnt = 0
    ans = 0
    for i in lst:
        if i == "R":
            rcnt += 1
            lcnt = 0
        else:
            lcnt += 1
            rcnt = 0
        if rcnt == 3:
            rcnt = 0
            ans += 1
        if lcnt == 3:
            lcnt = 0
            ans += 1
    print(ans)
for i in range(int(input())):
    solve()

from sys import exit,stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

T, = rl()
for _ in range(T):
    n, = rl()
    s = stdin.readline().rstrip()
    l = 1
    while l < n and s[l] == s[0]:
        l += 1
    if l == n:
        print((n + 2) // 3)
        continue
    r = n
    while s[r-1] == s[0]:
        r -= 1
    y = (n - r + l) // 3
    k = l
    for i in range(l, r):
        if s[i] != s[k]:
            y += (i - k) // 3
            k = i
    y += (r - k) // 3
    print(y)


import sys

T = int(sys.stdin.readline().strip())
for t in range (0, T):
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    ans = 0
    c = 1
    L = []
    for i in range (1, n):
        if s[i] == s[i-1]:
            c = c + 1
        else:
            L.append(c)
            c = 1
    if len(L) == 0:
        if c <= 2:
            print(0)
        else:
            print((c + 2) // 3)
    else:
        if len(L) % 2 == 0:
            L[0] = L[0] + c
        else:
            L.append(c)
        for l in L:
            ans = ans + l // 3
        print(ans)

t = int(input())
for i in range(t):
    n = int(input())
    s = list(input())

    ans = 0
    # print(set(s))
    if len(set(s)) != 1:
        ind = 0
        for i in range(1, n):
            if s[i] != s[i-1]:
                ind = i
                break
        S = s[ind:] + s[:ind]
        A = [1]
        for i in range(1, n):
            if S[i] != S[i-1]:
                A.append(1)
            else:
                A[-1] += 1
        # print(A)
        for i in range(len(A)):
            ans += A[i]//3
    
    else:
        ans = 1
        n -= 1

        ans += n//3
    print(ans)

t=int(input())
for _ in range(t):
    n=int(input())
    s=input()
    change=-1
    for i in range(n-1):
      if s[i]!=s[i+1]:
        change=i
        break
    if change==-1:
      
      print(-((-n)//3))
      continue
    streak=1
    ans=0
    for i in range(change,change+n):
      if s[(i)%n]==s[(i+1)%n]:
        streak+=1
      else:
        ans+=streak//3
        streak=1
    ans+=streak//3
    print(ans)

for _ in range(int(input())):
    n = int(input())
    s = input()
    if len(set(s)) == 1:
        print((n+2)//3)
        continue
    cur = 1
    arr = []
    for i in range(n):
        if s[i] == s[(i+1)%n]:
            cur += 1
        else:
            arr.append(cur)
            cur = 1
    if s[-1] == s[0]:
        arr[0] += cur-1
    res = 0
    for e in arr:
        res += e//3
    print(res)


from collections import defaultdict as dd
import math
import sys
import heapq
import copy
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


def solve():

	n =nn()

	s = input()

	streaks = []
	st = 1
	for i in range(n-1):
		if s[i]==s[i+1]:
			st+=1
		else:
			streaks.append(st)
			st = 1

	#print(st, s[0], s[n-1])
	if s[0]==s[n-1] and len(streaks)>0:
		streaks[0]+= st
	else:
		streaks.append(st)
	#print(streaks)
	moves= 0
	#print(streaks)
	if len(streaks)==1:
		moves = (streaks[0]-1)//3+1
	else:
		for num in streaks:
			moves += num//3

	print(moves)




q=nn()

for _ in range(q):
	solve()


import sys
input = sys.stdin.readline
for f in range(int(input())):
    n=int(input())
    s=input()
    s=s[0:n]
    mn=n
    for i in range(4):
        mins=[n]*4
        mins[i]=0
        if i<2 and s[0]=="L":
            mins[i]=1
        if i>1 and s[0]=="R":
            mins[i]=1
        for j in range(1,n):
            nmins=[n]*4
            nmins[0]=min(mins[2],mins[3])
            nmins[1]=mins[0]
            nmins[2]=mins[3]
            nmins[3]=min(mins[0],mins[1])
            if s[j]=="L":
                nmins[0]+=1
                nmins[1]+=1
            else:
                nmins[2]+=1
                nmins[3]+=1
            for k in range(4):
                mins[k]=nmins[k]
        if i==0:
            mn=min(mn,mins[2],mins[3])
        if i==1:
            mn=min(mn,mins[0])
        if i==2:
            mn=min(mn,mins[3])
        if i==3:
            mn=min(mn,mins[0],mins[1])
    print(mn)


def subsolve(a):
    n = len(a)
    dp = [[0] * 4 for _ in range(n + 1)]
    if a[0] == 'R':
        dp[0] = [0, n, n, n]
    else:
        dp[0] = [1, n, n, n]
    for i in range(1, n):
        dp[i][0] = min(dp[i - 1][2], dp[i - 1][3]) + int(a[i] != 'R')
        dp[i][1] = min(dp[i - 1][0], n) + int(a[i] != 'R')
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + int(a[i] != 'L')
        dp[i][3] = min(dp[i - 1][2], n) + int(a[i] != 'L')
    return min(dp[n - 1][2], dp[n - 1][3], n)

def solve():
    n = int(input())
    a = input()
    a += a
    ans = n
    for i in range(min(n, 4)):
        ans = min(ans, subsolve(a[i:i + n]))
    print(ans)

t = int(input())
for _ in range(t):
    solve()

def calc_one(n):
    frac = n / 3
    if frac % 1 == 0:
        return int(frac)
    return int(frac + 1)  # ceil

def calc_ops(L):
    frac = (L - 2) / 3
    if frac % 1 == 0:
        return int(frac)
    return int(frac + 1)    # ceil

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        s = input()
        l = []; c = 1
        for i in range(1, n):
            if s[i] == s[i - 1]:
                c += 1
            else:
                l.append(c)
                c = 1
        if s[0] == s[-1]:
            if len(l) == 0:
                l.append(c)
            else:
                l[0] += c
        else:
            l.append(c)
        if len(l) == 1:
            print(calc_one(n))
        else:
            total = 0
            for j in l:
                total += calc_ops(j)
            print(total)
main()

from itertools import groupby

def solve():
    n = int(input())
    s = input()

    if all(i == s[0] for i in s):
        print((n + 2) // 3)
        return
    
    if s[0] == s[-1]:
        if s[0] == 'R':
            idx = s.index('L')
            s = s[idx:] + 'R' * idx
        else:
            idx = s.index('R')
            s = s[idx:] + 'L' * idx
    
    res = 0
    for _, v in groupby(s):
        sz = len(list(v))
        res += sz // 3
    print(res)

for _ in range(int(input())):
    solve()



from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())
    S = stdin.readline()
    S = S[:-1]

    rnum = 0
    lnum = 0

    if "L" not in S or "R" not in S:
        print((n+2) // 3)
        continue

    for i in range(n-1):
        if S[i] != S[i+1]:
            S = S[i+1:] + S[:i+1]
            break

    ans = 0
    #print (S)
    for i in S:
        if i == "R":
            rnum += 1
            ans += (lnum)//3
            lnum = 0
        else:
            lnum += 1
            ans += (rnum)//3
            rnum = 0
            
    if lnum >= 3:
        ans += (lnum)//3
    if rnum >= 3:
        ans += (rnum)//3

    print (ans)