Comet OJ

C1751 [CCPC2017秦皇岛站-E] String of CCPC

内存限制：64 MB 时间限制：1000 ms

题目描述

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.

输入格式

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

输出

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

样例

样例输入 1

3
3
CCC
5
CCCCP
4
CPCP

样例输出 1

1
1
1

提示