BaoBao 在口袋里发现了一个长度为 $n$ 的字符串 $s$，该字符串仅由字符 ‘C’ 和 ‘P’ 组成。作为中国大学生程序设计竞赛（CCPC）的忠实粉丝，BaoBao 认为字符串 $s$ 的一个子串 $s_i s_{i+1} s_{i+2} s_{i+3}$ 是“好的”，当且仅当 $s_i = s_{i+1} = s_{i+3} = \text{'C'}$ 且 $s_{i+2} = \text{'P'}$，其中 $s_i$ 表示字符串 $s$ 中的第 $i$ 个字符。字符串 $s$ 的价值定义为 $s$ 中不同的“好”子串的数量。两个“好”子串 $s_i s_{i+1} s_{i+2} s_{i+3}$ 和 $s_j s_{j+1} s_{j+2} s_{j+3}$ 是不同的，当且仅当 $i \neq j$。

为了使这个字符串更有价值，BaoBao 决定从字符商店购买一些字符。每次他可以从商店购买一个 ‘C’ 或一个 ‘P’，并将其插入到 $s$ 中的任意位置。但一切皆有代价。如果这是 BaoBao 第 $i$ 次购买字符，他将需要花费 $(i - 1)$ 的价值。

BaoBao 最终获得的价值为 $s$ 的最终价值减去从商店购买所有字符的总花费。请帮助 BaoBao 最大化最终价值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示字符串 $s$ 的长度。 第二行包含字符串 $s$ ($|s| = n$)，由 ‘C’ 和 ‘P’ 组成。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 BaoBao 可以获得的最大最终价值。

样例

样例输入 1

3
3
CCC
5
CCCCP
4
CPCP

样例输出 1

1
1
1

说明

对于第一个样例，BaoBao 可以购买一个 ‘P’（花费 0），并将 $s$ 变为 “CCPC”。因此最终价值为 $1 - 0 = 1$。

对于第二个样例，BaoBao 可以购买一个 ‘C’ 和一个 ‘P’（花费 $0 + 1 = 1$），并将 $s$ 变为 “CCPCCPC”。因此最终价值为 $2 - 1 = 1$。

对于第三个样例，BaoBao 可以购买一个 ‘C’（花费 0），并将 $s$ 变为 “CCPCP”。因此最终价值为 $1 - 0 = 1$。

可以证明，对于这些样例，没有任何其他购买和插入字符的策略能获得更好的结果。