Milly is playing with some strings. She will take one random string S. She is interested to find such number of integers i ∈ [L_i , R_i] such that S_i = S_i+1 = S_i+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 L_i and R_i .

Output

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

Constraints

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