该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

题目描述

石头剪刀布是个经典游戏：石头赢剪刀，剪刀赢布，布赢石头，相同则平局。

Satori与Cirno正准备玩N局石头剪刀布。

Cirno的能力(?)是笨蛋，她只会提前想好N局游戏每次的出法，因为每次随机地想一个出法对她而言太困难了。

Satori的能力是读心，于是她决定让一让那个笨蛋：“我甚至可以先连续出若干个石头，然后是若干个布，最后是若干个剪刀。并且在这个限制下我已经想出了很多种战胜你的方法。”

这里“战胜”的意思是，在N局石头剪刀布中，赢的次数超过对方。

"若干个"可以是0个。

输入格式

第一行是一个正整数T，表示测试组数。

对于每组测试：

第一行是一个正整数N，表示石头剪刀布的局数。

第二行是一个长度为N的字符串S，表示Cirno的出法。S中只会出现大写字母'R','P','S',分别表示石头(Rock),布(Paper),剪刀(Scissors)。

输出格式

T行，每行一个整数，表示Satori可以战胜Cirno的方法数。

样例

输入

4
3
RPS
5
RPSPR
5
PPRSR
1
R
    

输出

3
5
1
1
    

数据范围与提示

对于Cirno的出法"RPS",有以下3种方法战胜她："RSS","PSS","PPS".

对于Cirno的出法"RPSPR",有以下5种方法战胜她："PSSSS","PPSSS","PPPPP","RSSSS","RRRPP"

对于Cirno的出法"PPRSR",有1种方法战胜她："PPPPP"

20%:N≤10,T≤5

50%:N≤100,T≤10

100%:N≤1000,T≤64

样例