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

题目背景

你说的对，但舞萌 DX 是一款由 SEGA 开发，华立科技代理，形似洗衣机的街机音乐游戏。

只要看准时机拍到所有的音符就好啦！

题目描述

在舞萌 DX 中，每个音符根据完成击打的时刻，会得到如下五种判定：

• Critical Perfect：简记为 P，可得 $3$ 分 dx 分。
• Perfect：简记为 p，可得 $2$ 分 dx 分。
• Great：简记为 G，可得 $1$ 分 dx 分。
• Good：简记为 g，不能得到 dx 分。
• Miss：简记为 m，不能得到 dx 分。

扶苏游玩了一局舞萌 DX，她将她各个音符的判定情况按顺序使用上面的简记规则记为了一个字符串 $s$。规定这个字符串最左边的字符表示第一个音符的判定结果，最右边的字符表示第 $|s|$ 个音符的判定结果，这里 $|s|$ 表示字符串 $|s|$ 的长度，也即整首歌的音符数。

现在，扶苏有 $q$ 次询问，每次询问会给出两个整数 $l, r$，对每个询问你需要回答：这首歌的第 $l$ 个音符到第 $r$ 个音符（包含第 $l$ 个和第 $r$ 个）的判定结果共能得到多少 dx 分数？

乐曲一段区间内的音符得到的 dx 分数是这些音符分别能得到的 dx 分数之和。

输入格式

本题单个测试点内有多组测试数据，输入的第一行是一个正整数，表示数据组数 $T$。对每组测试数据：

第一行是一个字符串 $s$（$1 \leq |s| \leq 10^7$），表示一首歌各个音符的判定结果。保证 $s$ 中只含字符 P，p，G，g，m。
第二行有一个整数 $q$（$1 \leq q \leq 10^4$），表示询问的数量。
接下来 $q$ 行，每行两个整数 $l, r$（$1 \leq l \leq r \leq |s|$），表示一组询问。

数据保证单个测试点内 $s$ 的长度之和不超过 $10^7$，$q$ 之和不超过 $10^4$。

输出格式

对每组测试数据，按询问的顺序依次给出每个询问的答案。每个询问输出一行一个整数表示答案。

2
PpGgm
2
1 5
4 5
PPppGGgm
5
1 2
3 4
5 6
7 7
8 8

6
0
6
4
2
0
0

提示说明

本题数据读入难度较大，建议使用以下模板。

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
typedef long long ll; //使用长整型，并使用“ll”为长整型的别名
ll n,a[N],q;
char buf;
namespace FastIO{
inline ll read(){
	int x=0,t=1;
	char ch;
	if(buf)ch=buf,buf=0; //如果上一次读到了数字，优先使用上一次读入的结果
	else ch=getchar();
	while(ch<48||ch>57){
	    if(ch=='-')
		t=-1;
		ch=getchar();
	}
	while(ch>47&&ch<58){
		x=x*10+ch-48,ch=getchar();
	}
	return x*t;
}
}
using namespace FastIO;
int main(){
	ll T=read();
	while(T--){
		char p;
		int i=0;
		while(p=getchar(),++i){
			if(p>='0'&&p<='9'){ //读到数字，退出字符读入，进行询问
				buf=p;
				break;
			}
      //进行处理，替换成你的代码
		}
		n=i;
		q=read();
		while(q--){
			ll x=read(),y=read();
			//进行处理，替换成你的代码
		}
	}
}