Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">*n*</sub> (*n* is the length of the string), consisting only of characters "." and "#" and *m* queries. Each query is described by a pair of integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> &lt; *r*<sub class="lower-index">*i*</sub> ≤ *n*). The answer to the query *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> is the number of such integers *i* (*l*<sub class="lower-index">*i*</sub> ≤ *i* &lt; *r*<sub class="lower-index">*i*</sub>), that *s*<sub class="lower-index">*i*</sub> = *s*<sub class="lower-index">*i* + 1</sub>.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.
The first line contains string *s* of length *n* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>) — the number of queries. Each of the next *m* lines contains the description of the corresponding query. The *i*-th line contains integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> &lt; *r*<sub class="lower-index">*i*</sub> ≤ *n*).
import sys

SEPARATOR = "\n"
UNICODE = "utf-8"


def get_longest_prefix_length(word) -> int:
    length = 0
    for i in range(len(word) + 1):
        if word[0:i] == word[:i][::-1]:
            length = i
    return length


class PrefSumA:
    def __init__(self, string: str):
        self.string = string
        self.string_len = len(self.string)
        self.pref_sum = self._get_pref_sum()

    def _get_pref_sum(self):
        pref_sum = [0] * self.string_len
        for i in range(1, self.string_len):
            pref_sum[i] = (
                pref_sum[i - 1] + 1
                if self.string[i - 1] == self.string[i]
                else pref_sum[i - 1]
            )
        return pref_sum

    def process(self, left: int, right: int) -> int:
        return self.pref_sum[right-1] - self.pref_sum[left-1]


lines = sys.stdin.buffer.readlines()
string = lines[0].decode(UNICODE).strip()
pref_sum_a = PrefSumA(string)
result = [
    str(pref_sum_a.process(int(l), int(r)))
    for word in lines[2:]
    for l, r in [word.decode(UNICODE).strip().split()]
]


encoded_array = (SEPARATOR.join(result)).encode(UNICODE)
sys.stdout.buffer.write(encoded_array)
					 	 	  	   			     	  			 	