milly-and-strings

Milly is playing with some strings. She will take one random string S. She is interested to find such number of integers i ∈ [Li , Ri] such that Si = Si+1 = Si+2 . Your task is to help Milly in this problem.

Input

First line of the input will contain T (No. of test cases).
For each test case, first line will contain a string S.
Next line will contain an integer Q (No. of queries) and then next each Q lines will contain two space separated integers Li and Ri .

Output
For every query, print the answer in a new line.
Constraints

1 ≤ T ≤ 5
3 ≤| S| ≤ 10^5
1 ≤ Q ≤ 10^5<>
1 ≤ Li ≤ Ri  ≤ |S|-2
Here || denotes the length of the string and characters of S ∈ {a, b, c ..., z}

SAMPLE INPUT
1
aaaaaa
3
1 2
1 3
1 4

SAMPLE OUTPUT
2
3
4

Source: hackerearth | Difficulty: EASY


Solutions: