Problem: 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 = s1s2... sn (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers li, ri (1 ≤ li < ri ≤ n). The answer to the query li, ri is the number of such integers i (li ≤ i < ri), that si = si + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

Input

The first line contains string s of length n (2 ≤ n ≤ 105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers li, ri (1 ≤ li < ri ≤ n).

Output

Print m integers — the answers to the queries in the order in which they are given in the input.

Examples

Input

......
4
3 4
2 3
1 6
2 6


Output

1
1
5
4


Input

#..###
5
1 3
5 6
1 5
3 6
3 4


Output

1
1
2
2
0

Solution (in PYTHON3):

Solution:
class CodeforcesTask313BSolution:
    def __init__(self):
        self.result = ''
        self.string = ''
        self.m = 0
        self.queries = []

    def read_input(self):
        self.string = input()
        self.m = int(input())
        for x in range(self.m):
            self.queries.append([int(x) for x in input().split(" ")])

    def process_task(self):
        n = len(self.string)
        dp_point = [0] * n
        dp_hash = [0] * n
        if self.string[0] == ".":
            dp_point[0] = 1
        else:
            dp_hash[0] = 1
        for x in range(1, n):
            if self.string[x] == ".":
                dp_point[x] = dp_point[x - 1] + 1
                dp_hash[x] = dp_hash[x - 1]
            else:
                dp_point[x] = dp_point[x - 1]
                dp_hash[x] = dp_hash[x - 1] + 1
        for x in range(n - 1, 0, -1):
            dp_point[x] -= dp_point[x - 1]
            dp_hash[x] -= dp_hash[x - 1]
        dp_cons_point = [0] * n
        dp_cons_hash = [0] * n
        lastp = self.string[0] == "."
        for x in range(1, n):
            if lastp and self.string[x] == ".":
                dp_cons_point[x] = dp_cons_point[x - 1] + 1
                dp_cons_hash[x] = dp_cons_hash[x - 1]
            elif not lastp and not self.string[x] == ".":
                dp_cons_point[x] = dp_cons_point[x - 1]
                dp_cons_hash[x] = dp_cons_hash[x - 1] + 1
            else:
                dp_cons_point[x] = dp_cons_point[x - 1]
                dp_cons_hash[x] = dp_cons_hash[x - 1]
            lastp = self.string[x] == "."
        for query in self.queries:
            print(dp_cons_point[query[1] - 1] - dp_cons_point[query[0] - 1] + dp_cons_hash[query[1] - 1] - dp_cons_hash[query[0] - 1])
        #print(dp_point, dp_hash)
        #print(dp_cons_point, dp_cons_hash)

    def get_result(self):
        return self.result


if __name__ == "__main__":
    Solution = CodeforcesTask313BSolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())