You are given a string S, each character of which is either \verb+N+ or \verb+P+. In one move, you can perform the following operation:

Pick an index 1 ≤ i ≤ |S| and flip S_{i}, i.e, if S_{i} = \verb+N+ set it to \verb+P+ and vice versa.

Find the minimum number of moves required to obtain a string such that there exists a way to split it into several continuous substrings, each of which is either \verb+P+ or \verb+NP+, and the number of \verb+P+ substrings in this splitting equals the number of \verb+NP+ substrings.

For example, \verb+NPP+ and \verb+PNPPNP+ can be split this way (into \verb+NP+ + \verb+P+ and \verb+P+ + \verb+NP+ + \verb+P+ + \verb+NP+ respectively) but \verb+NNPP+ cannot.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first and only line of input of each test case contains the string S.

------ Output Format ------ 

For each test case, output a single line containing one integer — the minimum number of moves required to transform the string into the desired form.

------ Constraints ------ 

$1 ≤ T ≤ 3.5 \cdot 10^{4}$
$3 ≤ |S| ≤ 10^{5}$
$S$ contains only characters $\verb+N+$ and $\verb+P+$
$|S|$ is a multiple of $3$
- Sum of $|S|$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
3
NNN
PNP
NPNPNPNNP

----- Sample Output 1 ------ 
2
0
2
----- explanation 1 ------ 
Test Case $1$: Flip the second and third characters so that the string becomes $\verb+NPP+$, which can be broken into substrings $\verb+NP+$ + $\verb+P+$. Here the count of substrings of both types is $1$.

Test Case $2$: The original string can already be split into $\verb+P+$ + $\verb+NP+$, so no more moves are required.

Test Case $3$: Flip the first and eighth characters so that the string becomes $\verb+PPNPNPNPP+$, which can be broken into substrings $\verb+P+$ + $\verb+P+$ + $\verb+NP+$ + $\verb+NP+$ + $\verb+NP+$ + $\verb+P+$. Here the count of substrings of both types is $3$.

Difficulty: VERY_HARD
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
while t > 0:
	S = list(input())
	l = len(S)
	Fans = 0
	if S[-1] == 'N':
		Fans = 1
		S[-1] = 'P'
	for i in range(1, l):
		if S[i] == 'N' and S[i - 1] == 'N':
			S[i] = 'P'
			Fans += 1
	nc = S.count('N')
	ans = Fans + abs(l // 3 - nc)
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	s = list(input())
	l = len(s)
	c = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		c = 1
	for j in range(l):
		if j - 1 >= 0 and s[j - 1] == 'N' and (s[j] == 'N'):
			s[j] = 'P'
			c += 1
	c2 = 0
	r = l // 3
	for k in range(l):
		if s[k] == 'N':
			c2 += 1
	c += abs(r - c2)
	print(int(c))


t = int(input())
for _ in range(t):
	s = list(input())
	l = len(s)
	final_count = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		final_count = 1
	for i in range(l):
		if i - 1 >= 0 and s[i - 1] == 'N' and (s[i] == 'N'):
			s[i] = 'P'
			final_count += 1
	countN = 0
	reqN = l // 3
	for i in range(l):
		if s[i] == 'N':
			countN += 1
	final_count += abs(reqN - countN)
	print(int(final_count))


t = int(input())
L = []
for _ in range(0, t):
	s = list(input())
	l = len(s)
	finalcount = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		finalcount += 1
	for i in range(0, l):
		if i >= 1 and s[i] == 'N' and (s[i - 1] == 'N'):
			s[i] = 'P'
			finalcount += 1
	countN = 0
	reqN = l // 3
	for i in range(0, l):
		if s[i] == 'N':
			countN += 1
	finalcount += abs(reqN - countN)
	L.append(finalcount)
print(*L, sep='\n')


from collections import Counter
from functools import reduce
t = int(input())
for _ in range(t):
	a = list(input())
	(n, c, inv) = (len(a), len(a) // 3, 0)
	if a[-1] == 'N':
		inv += 1
		a[-1] = 'P'
	cn = 0
	for el in a:
		if el == 'N':
			cn += 1
		else:
			kp = min(c, (cn + 1) // 2)
			inv += cn - kp
			c -= kp
			cn = 0
	print(inv + c)


for tc in range(int(input())):
	s = list(input())
	x = 0
	(p, n) = (0, 0)
	np = 0
	req = len(s) // 3
	while x < len(s) - 1 and np < req:
		if s[x] + s[x + 1] == 'NP':
			if np < req:
				s[x] = '-'
				s[x + 1] = '-'
				np += 1
				x += 2
			else:
				break
				x += 1
		else:
			x += 1
	ct = 0
	x = 0
	while x < len(s) - 1 and np < req:
		if s[x] + s[x + 1] == 'NN':
			if np < req:
				ct += 1
				s[x] = '-'
				s[x + 1] = '-'
				np += 1
				x += 2
			else:
				break
				x += 1
		else:
			x += 1
	x = 0
	while x < len(s) - 1 and np < req:
		if s[x] + s[x + 1] == 'PP':
			if np < req:
				ct += 1
				s[x] = '-'
				s[x + 1] = '-'
				np += 1
				x += 2
			else:
				break
				x += 1
		else:
			x += 1
	x = 0
	while x < len(s) - 1 and np < req:
		if s[x] + s[x + 1] == 'PN':
			if np < req:
				ct += 2
				s[x] = '-'
				s[x + 1] = '-'
				np += 1
				x += 2
			else:
				break
				x += 1
		else:
			x += 1
	for x in s:
		if x == 'N':
			ct += 1
	print(ct)


for _ in range(int(input())):
	s = input()
	n_no = s.count('N')
	p_no = s.count('P')
	cnt = 0
	if s[-1] == 'N':
		cnt += 1
		n_no -= 1
		p_no += 1
	s = s[:len(s) - 1] + 'P'
	nn_no = 0
	i = 0
	while i < len(s):
		if s[i:i + 2] == 'NN':
			nn_no += 1
			i += 1
		i += 1
	n_no -= nn_no
	p_no += nn_no
	cnt += nn_no
	n = len(s) // 3
	if n_no == n:
		print(cnt)
	elif n_no < n:
		cnt = cnt + n - n_no
		print(cnt)
	elif n_no > n:
		cnt = cnt + n_no - n
		print(cnt)


def recorrer_texto(texto: str):
	count = 0
	l_texto = list(texto)
	if len(texto) % 3:
		return -1
	elif texto[-1] == 'N':
		l_texto[-1] = 'P'
		count += 1
	for i in range(len(texto) - 1):
		if l_texto[i] == 'N' and l_texto[i + 1] == 'N':
			l_texto[i + 1] = 'P'
			count += 1
	return count + abs(l_texto.count('N') - len(texto) // 3)
for _ in range(int(input())):
	print(recorrer_texto(str(input())))


for _ in range(int(input())):
	s = list(input())
	(ans, nct) = (0, 0)
	reqd = len(s) // 3
	if s[-1] == 'N':
		ans = 1
		s[-1] = 'P'
	for c in s:
		if c == 'P':
			keep = min(reqd, (nct + 1) // 2)
			ans += nct - keep
			reqd -= keep
			nct = 0
		else:
			nct += 1
	print(ans + reqd)


for _ in range(int(input())):
	s = input()
	n = len(s)
	li = []
	for i in range(n):
		li.append(s[i])
	f = 0
	for i in range(len(s) - 1):
		if li[i] == 'N':
			if li[i + 1] == 'N':
				f = f + 1
				li[i + 1] = 'P'
	if li[-1] == 'N':
		f = f + 1
		li[-1] = 'P'
	c = 0
	for i in range(n):
		if li[i] == 'P':
			c = c + 1
	f = f + abs(n - c - n // 3)
	print(f)


import math
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	s = list(S())
	n = len(s)
	ans = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		ans += 1
	for i in range(n - 1):
		if s[i] == 'N' and s[i + 1] != 'P':
			ans += 1
			s[i + 1] = 'P'
	c1 = s.count('N')
	print(ans + abs(c1 - n // 3))


import sys

def count_flips(n, string):
	flips = 0
	string = list(string)
	for i in range(1, n):
		if string[i - 1] == 'N' and string[i] == 'N':
			string[i] = 'P'
			flips += 1
		if i == n - 1 and string[i] == 'N':
			string[i] = 'P'
			flips += 1
	freq_n = 0
	freq_p = 0
	for i in range(n):
		if string[i] == 'N':
			freq_n += 1
	freq_p = n - freq_n
	flips += abs(n // 3 - freq_n)
	return flips

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		string = sys.stdin.readline().strip('\n')
		n = len(string)
		print(count_flips(n, string))
main()


def solve(s, n):
	flips = 0
	for i in range(1, n):
		if s[i] == 'N' and s[i - 1] == 'N':
			s = s[:i] + 'P' + s[i + 1:]
			flips += 1
	if s[n - 1] == 'N':
		flips += 1
		s = s[:-1] + 'P'
	cnp = s.count('NP')
	cp = s.count('P')
	if cnp == n // 3 and cp == n - n // 3:
		return flips
	diff = abs(cnp - n // 3)
	flips += diff
	return flips
t = int(input())
for _ in range(t):
	s = input()
	ans = solve(s, len(s))
	print(ans)


from collections import defaultdict as dd

def solve(S):
	ln = len(S)
	x = ln // 3
	C = dd(int)
	ind = 0
	while ind < len(S):
		if ind + 1 < len(S):
			cur = S[ind:ind + 2]
		else:
			cur = S[ind]
		if cur in ('NP', 'NN', 'PP'):
			C[cur] += 1
			ind += 2
		else:
			C[S[ind]] += 1
			ind += 1
	if C['NP'] == x:
		return 2 * C['NN'] + C['N']
	if C['NP'] < x:
		gap = x - C['NP']
		sub = min(gap, C['NN'])
		change = sub
		C['NN'] -= sub
		gap -= sub
		sub = min(gap, C['PP'])
		change += sub
		gap -= sub
		C['PP'] -= sub
		assert gap == 0
		return change + 2 * C['NN'] + C['N']
	else:
		gap = C['NP'] - x
		return gap + 2 * C['NN'] + C['N']
for case in range(int(input())):
	S = input()
	ans = solve(S)
	print(ans)


def solve():
	s = list(input())
	len_s = len(s)
	ans = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		ans += 1
	for i in range(len_s - 1):
		if s[i] == 'N' and s[i + 1] != 'P':
			ans += 1
			s[i + 1] = 'P'
	cnt_n = s.count('N')
	print(ans + abs(cnt_n - len_s // 3))
T = int(input())
for i in range(T):
	solve()


for t in range(int(input())):
	s = list(input())
	l = len(s)
	ans = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		ans += 1
	for i in range(l - 1):
		if s[i] == 'N' and s[i + 1] == 'N':
			s[i + 1] = 'P'
			ans += 1
	p = 1
	np = 0
	for i in range(l - 1):
		if s[i] == 'N':
			np += 1
			p -= 1
		else:
			p += 1
	if p == np:
		print(ans)
	elif p > np:
		print(ans + (p - np) // 3)
	else:
		print(ans + (np - p) // 3)


def main():
	s = list(input())
	l = len(s)
	ans = 0
	if s[-1] == 'N':
		s[-1] = 'P'
		ans += 1
	for i in range(l - 1):
		if s[i] == 'N' and s[i + 1] == 'N':
			s[i + 1] = 'P'
			ans += 1
	p = 1
	np = 0
	for i in range(l - 1):
		if s[i] == 'N':
			np += 1
			p -= 1
		else:
			p += 1
	if p == np:
		return ans
	elif p > np:
		return ans + (p - np) // 3
	else:
		return ans + (np - p) // 3
for _ in range(int(input())):
	print(main())


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 200001
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v

def checkPrime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	s = list(str(input()))
	n = len(s)
	k = n // 3
	v = [False for _ in range(n)]
	c = 0
	ans = 0
	for i in range(n - 1):
		if s[i] == 'N' and s[i + 1] == 'P' and (c < k):
			v[i] = True
			v[i + 1] = True
			c += 1
	for i in range(n - 1):
		if c < k and v[i] == False and (v[i + 1] == False) and (s[i] == 'N') and (s[i + 1] == 'N'):
			s[i + 1] = 'P'
			c += 1
			ans += 1
			v[i] = True
			v[i + 1] = True
	for i in range(n - 1):
		if c < k and v[i] == False and (v[i + 1] == False) and (s[i] == 'P') and (s[i + 1] == 'P'):
			s[i] = 'N'
			c += 1
			ans += 1
			v[i] = True
			v[i + 1] = True
	for i in range(n):
		if not v[i] and s[i] == 'N':
			s[i] = 'P'
			v[i] = True
			ans += 1
	if c != k:
		ans += 1
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	ans = 0
	if a[-1] == 'N':
		a[-1] = 'P'
		ans += 1
	countnp = 0
	for i in range(n - 1):
		countnp += a[i] + a[i + 1] == 'NP'
	(countn, countp) = (0, 0)
	for i in range(n):
		countn += a[i] == 'N'
		countp += a[i] == 'P'
	if countnp > n // 3:
		ans += countn - n // 3
	else:
		for i in range(1, n - 1):
			if a[i] == 'N' and a[i - 1] == 'N':
				a[i] = 'P'
				countp += 1
				ans += 1
		ans += abs(countp - (n - n // 3))
	return ans
for T in range(int(input())):
	a = list(input().strip())
	n = len(a)
	print(answer())


def fun(a, b, c, d, e, f):
	if c >= f:
		return c - f + 2 * d + e
	res = f - c
	if d >= res:
		return res + 2 * (d - res) + e
	res1 = res - d
	if res1 <= a:
		return e + res
	return d + a + (res - d - a) + (res - d - a)
for _ in range(int(input())):
	s = list(input())
	n = len(s)
	cpp = 0
	cp = 0
	no = 0
	npp = 0
	a = 0
	i = 0
	while i < n:
		if s[i] == 'P':
			if i + 1 < n and s[i + 1] == 'P':
				cpp += 1
				i += 1
			else:
				cp += 1
		elif i + 1 < n and s[i + 1] == 'P':
			npp += 1
			i += 1
		elif i + 1 < n and s[i + 1] == 'N':
			a += 1
			i += 1
		else:
			no += 1
		i += 1
	print(fun(cpp, cp, npp, a, no, n // 3))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	s = st()
	N = len(s)
	i = n = nn = p = np = pp = 0
	while i < N:
		if s[i] == 'P':
			if i + 1 < N and s[i + 1] == 'P':
				pp += 1
				i += 1
			else:
				p += 1
		elif i + 1 < N and s[i + 1] == 'P':
			np += 1
			i += 1
		elif i + 1 < N and s[i + 1] == 'N':
			nn += 1
			i += 1
		else:
			n += 1
		i += 1
	req = N // 3
	if np >= req:
		pr(np - req + 2 * nn + n)
	else:
		left = req - np
		if nn >= left:
			pr(2 * nn - left + n)
		else:
			x = left - nn
			if pp >= x:
				pr(left + n)
			else:
				pr(2 * left - nn - pp)
for _ in range(inp()):
	solve()


import math
import sys
yhuji = sys.stdin.readline
FC = lambda : yhuji().rstrip()
AS = lambda : int(FC())
FT = lambda : map(int, FC().split())
L = lambda : list(FT())
polk4 = 1000000007
polk5 = 998244353
for _ in range(AS()):
	aswed = list(FC())
	deswqa = len(aswed)
	cdfret = 0
	if aswed[-1] == 'N':
		aswed[-1] = 'P'
		cdfret += 1
	for hyujnm in range(deswqa - 1):
		if aswed[hyujnm] == 'N' and aswed[hyujnm + 1] != 'P':
			cdfret += 1
			aswed[hyujnm + 1] = 'P'
	hbny4 = aswed.count('N')
	print(cdfret + abs(hbny4 - deswqa // 3))


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []
gp = []
ans = []
f = 0
w = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def dfs(i, prod, rem, n):
	if rem == 0:
		while i < len(n):
			prod *= int(n[i])
			i += 1
		return prod
	if i == len(n):
		return prod
	mx = 0
	for j in range(9 - int(n[i])):
		mx = max(dfs(i + 1, (int(n[i]) + min(j, rem)) * prod, rem - min(j, rem), n), mx)
	return mx

def hnbhai(tc):
	s = list(sa())
	n = len(s)
	last = []
	tot = 0
	tnp = 0
	p = 0
	for i in range(n):
		if s[i] == 'N':
			tot += 1
		if s[i] == 'P':
			if tot >= 1:
				tnp += 1
			tot -= 1
			if tot >= 1:
				last.append(tot)
			tot = 0
	p = s.count('P') - tnp
	last.append(tot)
	ans = 0
	x = 0
	for i in last:
		ans += (i + 1) // 2
		if i % 2:
			p += 1
		tnp += i // 2
	if tnp > p:
		print(ans + (n // 3 - p) // 2)
		return
	print(ans + (n // 3 - tnp))
for _ in range(sb()):
	hnbhai(_ + 1)


for _ in range(int(input())):
	S = list(input())
	n = len(S)
	Nexcess = S.count('N') - n // 3
	NseriesStarted = False
	odd = False
	moves = 0
	for i in range(n):
		if S[i] == 'N':
			if NseriesStarted:
				if odd:
					S[i] = 'P'
					moves += 1
					odd = False
				else:
					odd = True
			else:
				NseriesStarted = True
				odd = True
		elif NseriesStarted:
			NseriesStarted = False
	if S[-1] == 'N':
		moves += 1
	if Nexcess >= moves:
		print(Nexcess)
	else:
		print(2 * moves - Nexcess)


from sys import stdin, stdout, setrecursionlimit as srl
from threading import stack_size
from collections import deque, defaultdict as dd
from math import gcd, ceil, sqrt
from bisect import bisect_left as lb
from bisect import bisect_right as rb
flush = stdout.flush
p = int(1000000000.0 + 7)
tc = 1
tc = int(input())
for _ in range(1, tc + 1):
	s = input()
	n = len(s) // 3
	l = [i for i in s]
	ans = 0
	for i in range(len(l) - 1):
		if l[i] == l[i + 1] and l[i] == 'N':
			ans += 1
			l[i + 1] = 'P'
	if l[-1] == 'N':
		l[-1] = 'P'
		ans += 1
	s = ''
	for i in l:
		s = s + i
	(p, np) = (0, 0)
	for i in s:
		if i == 'N':
			np += 1
	print(ans + abs(n - np))


from collections import defaultdict
ans = ''
for _ in range(int(input())):
	st = input()
	d = {'NP': 0, 'P': 0, 'N': 0}
	count = 0
	i = 0
	while i < len(st):
		if i < len(st) - 1 and st[i] == 'N' and (st[i + 1] == 'N'):
			count += 1
			d['NP'] += 1
			i += 1
		elif i < len(st) - 1 and st[i] == 'N' and (st[i + 1] == 'P'):
			d['NP'] += 1
			i += 1
		elif st[i] == 'P':
			d['P'] += 1
		elif st[i] == 'N':
			d['P'] += 1
			count += 1
		i += 1
	t = abs(d['NP'] - d['P']) / 3
	if t % 1 == 0:
		count += int(t)
	else:
		count = -1
	ans += str(count) + '\n'
print(ans)


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def bs(arr, le, ri):
	l = 0
	arr.sort()
	r = len(arr) - 1
	ans = 10000000
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= le and arr[m] <= ri:
			ans = arr[m]
			r = m - 1
		elif arr[m] < le:
			l = m + 1
		else:
			r = m - 1
	return ans
t = int(input())
while t > 0:
	s = input().strip()
	f = 0
	if s[-1] == 'N':
		f += 1
	n = len(s)
	i = n - 2
	while i > 0:
		if s[i] == 'N' and s[i - 1] == 'N':
			f += 1
			i -= 1
		i -= 1
	p = s.count('P') + f
	print(f + abs(2 * n // 3 - p))
	t -= 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	(ans, count) = (0, 0)
	s = list(s)
	for i in range(1, n):
		if s[i] == 'N' and s[i - 1] == 'N':
			s[i] = 'P'
			ans += 1
		elif s[i] == 'N' and i == n - 1:
			s[i] = 'P'
			ans += 1
		if s[i] == 'N':
			count += 1
	if s[0] == 'N':
		count += 1
	ans += abs(n // 3 - count)
	print(ans)