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*_{1}*s*_{2}... *s*_{*n*}$ ($*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*_{*i*}, *r*_{*i*}$ $(1 ≤ *l*_{*i*} < *r*_{*i*} ≤ *n*)$. The answer to the query $*l*_{*i*}, *r*_{*i*}$ is the number of such integers $*i*$ $(*l*_{*i*} ≤ *i* < *r*_{*i*})$, that $*s*_{*i*} = *s*_{*i* + 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* ≤ 10^{5})$. It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer $*m*$ $(1 ≤ *m* ≤ 10^{5})$ — the number of queries. Each of the next $*m*$ lines contains the description of the corresponding query. The $*i*$-th line contains integers $*l*_{*i*}, *r*_{*i*}$ $(1 ≤ *l*_{*i*} < *r*_{*i*} ≤ *n*)$.

Output

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