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*).
from typing import List, Union
from collections import namedtuple
import sys
import traceback
from datetime import datetime
from time import perf_counter


class Solution:
    def __init__(self, data_str: str):
        self.memo = [0 for _ in range(len(data_str))]
        for index in range(1, len(data_str)):
            if data_str[index] == data_str[index - 1]:
                self.memo[index] = self.memo[index - 1] + 1
            else:
                self.memo[index] = self.memo[index - 1]

    def ilya_query(self, left, right):
        result = self.memo[right - 1] - self.memo[left - 1]
        print(result)
        return result


TestCase = namedtuple('TestCase', 'left right correct')


def read_test_cases(input_file, output_file):
    data_str = []
    test_cases = []
    try:
        with open(input_file) as in_f:
            with open(output_file) as out_f:
                while True:
                    c = in_f.read(1)
                    if c == '\n' or c == ' ':
                        break
                    data_str.append(c)
                data_str = ''.join(data_str)
                test_num = int(in_f.readline())
                for _ in range(test_num):
                    items = in_f.readline().strip().split(' ')
                    left = int(items[0])
                    right = int(items[1])
                    correct = int(out_f.readline().strip())
                    test_cases.append(TestCase(left, right, correct))
        # raise Exception('My Test Exception')
    except Exception as exc:
        exc_name = exc.__class__.__name__
        exc_msg = str(exc)
        exc_info = sys.exc_info()
        print('EXCEPTION:', exc_name, exc_msg)
        traceback.print_exception(*exc_info)
    return data_str, test_cases


def run_test_cases(data_str: str, test_cases: List[TestCase]):
    solution = Solution(data_str)
    for t in test_cases:
        result = solution.ilya_query(t.left, t.right)
        print('STR:', data_str, 'LEFT:', t.left, 'RIGHT:', t.right,
              'CORRECT:', t.correct, 'RESULT:', result, 'CHECK:', result == t.correct)


if __name__ == '__main__':
    if len(sys.argv) > 1 and '--debug' in sys.argv:
        time_str = datetime.utcnow().strftime('%Y.%m.%d %H:%M:%S')
        print('STARTING:', time_str)
        data_str, test_cases = read_test_cases('data/input.txt', 'data/output.txt')
        start_counter = perf_counter()
        run_test_cases(data_str, test_cases)
    else:
        data_str = []
        while True:
            c = sys.stdin.read(1)
            if c == '\n' or c == ' ':
                break
            data_str.append(c)
        data_str = ''.join(data_str)
        test_num = int(input())
        solution = Solution(data_str)
        for _ in range(test_num):
            items = input().strip().split(' ')
            left = int(items[0])
            right = int(items[1])
            solution.ilya_query(left, right)
