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.

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*).

提交代码