题目背景

你说的对，但舞萌 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