dx分计算(DX Score Calculation)

题目描述

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

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

扶苏游玩了一局舞萌 DX，她将她各个音符的判定情况按顺序使用上面的简记规则记为了一个字符串 $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$。

输出格式

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

样例输入 #1

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

样例输出 #1

6
0
6
4
2
0
0

数据范围

对于 $100\%$ 的数据，$1 \leq |s| \leq 10^7$，$1 \leq q \leq 10^4$，$1 \leq l \leq r \leq |s|$，$s$ 中只含字符 P、p、G、g、m。

知识点与难度

本题涉及的知识点从属于 GESP三级（字符串、一维数组、前缀和），难度等级：普及-。