Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
149 - The 2017 China Collegiate Programming Contest, Qinhuangdao Site - E
String of CCPC

Time Limit: 1 Second      Memory Limit: 65536 KB

BaoBao has just found a string $$s$$ of length $$n$$ consisting of 'C' and 'P' in his pocket. As a big fan of the China Collegiate Programming Contest, BaoBao thinks a substring $$s_is_{i+1}s_{i+2}s_{i+3}$$ of $$s$$ is "good", if and only if $$s_i = s_{i+1} = s_{i+3} =$$ 'C', and $$s_{i+2} =$$ 'P', where $$s_i$$ denotes the $$i$$-th character in string $$s$$. The value of $$s$$ is the number of different "good" substrings in $$s$$. Two "good" substrings $$s_is_{i+1}s_{i+2}s_{i+3}$$ and $$s_js_{j+1}s_{j+2}s_{j+3}$$ are different, if and only if $$i \ne j$$.

To make this string more valuable, BaoBao decides to buy some characters from a character store. Each time he can buy one 'C' or one 'P' from the store, and insert the character into any position in $$s$$. But everything comes with a cost. If it's the $$i$$-th time for BaoBao to buy a character, he will have to spend $$i-1$$ units of value.

The final value BaoBao obtains is the final value of $$s$$ minus the total cost of all the characters bought from the store. Please help BaoBao maximize the final value.

#### Input

There are multiple test cases. The first line of the input contains an integer $$T$$, indicating the number of test cases. For each test case:

The first line contains an integer $$n$$ ($$1 \le n \le 2\times 10^5$$), indicating the length of string $$s$$.

The second line contains the string $$s$$ ($$|s| = n$$) consisting of 'C' and 'P'.

It's guaranteed that the sum of $$n$$ over all test cases will not exceed $$10^6$$.

#### Output

For each test case output one line containing one integer, indicating the maximum final value BaoBao can obtain.

#### Sample Input

3
3
CCC
5
CCCCP
4
CPCP

#### Sample Output

1
1
1

#### Hint

For the first sample test case, BaoBao can buy one 'P' (cost 0 value) and change $$s$$ to "CCPC". So the final value is 1 - 0 = 1.

For the second sample test case, BaoBao can buy one 'C' and one 'P' (cost 0 + 1 = 1 value) and change $$s$$ to "CCPCCPC". So the final value is 2 - 1 = 1.

For the third sample test case, BaoBao can buy one 'C' (cost 0 value) and change $$s$$ to "CCPCP". So the final value is 1 - 0 = 1.

It's easy to prove that no strategies of buying and inserting characters can achieve a better result for the sample test cases.

Submit    Status