Background

You are right, but maimai DX is an arcade music game developed by SEGA and operated by Wah Li Technology, and it looks like a washing machine.

You just need to hit all the notes at the right time.

Problem Description

In maimai DX, each note will receive one of the following five judgments depending on when it is hit:

• Critical Perfect: abbreviated as P, gives $3$ dx points.
• Perfect: abbreviated as p, gives $2$ dx points.
• Great: abbreviated as G, gives $1$ dx point.
• Good: abbreviated as g, gives no dx points.
• Miss: abbreviated as m, gives no dx points.

Fusu played a game of maimai DX. She recorded the judgment of each note in order using the abbreviations above, forming a string $s$. The leftmost character of this string represents the judgment of the first note, and the rightmost character represents the judgment of the $|s|$-th note, where $|s|$ is the length of the string, i.e., the total number of notes in the song.

Now, Fusu has $q$ queries. Each query gives two integers $l, r$. For each query, you need to answer: how many dx points can be obtained in total from the judgments of the $l$-th note to the $r$-th note (including both the $l$-th and the $r$-th notes)?

The dx points of notes in a segment of the song equal the sum of the dx points that each note in the segment can obtain.

Input Format

This problem has multiple sets of testdata within a single test point. The first line of the input is a positive integer, representing the number of test cases $T$. For each test case:

The first line is a string $s$ ($1 \leq |s| \leq 10^7$), representing the judgment results of all notes in a song. It is guaranteed that $s$ contains only the characters P, p, G, g, m.
The second line contains an integer $q$ ($1 \leq q \leq 10^4$), representing the number of queries.
The next $q$ lines each contain two integers $l, r$ ($1 \leq l \leq r \leq |s|$), representing one query.

It is guaranteed that within a single test point, the total length of all $s$ does not exceed $10^7$, and the total sum of all $q$ does not exceed $10^4$.

Output Format

For each test case, output the answers to the queries in order. Output one integer per line for each query.

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

Hint

Translated by ChatGPT 5