#152Easy

Ilya and queries

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given a string $s_1 s_2 \ldots s_n$ of characters . and #. For every query $(l, r)$ find the number of indices $i$ such that $l \le i < r$ and $s_i = s_{i+1}$ .

Input format

The first line contains the string $s$ ( $2 \le n \le 10^5$ ). The second line contains $m$ ( $1 \le m \le 10^5$ ). The next $m$ lines contain $l$ and $r$ ( $1 \le l < r \le n$ ).

Output format

For every query print one number on a separate line.

Examples

Input

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

Output

Input

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

Output

Note

Let $c_i = 1$ if $s_i = s_{i+1}$ and $0$ otherwise. The answer is $c_l + \ldots + c_{r-1}$ , that is $p_{r-1} - p_{l-1}$ with prefix sums of $c$ . Watch the indices: $i = r$ is not counted.

In the first query of the second example (#..) only $s_2 = s_3$ works — the answer is $1$ .

Source: Codeforces, problem 313B.

Ilya and queries

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given a string $s_1 s_2 \ldots s_n$ of characters . and #. For every query $(l, r)$ find the number of indices $i$ such that $l \le i < r$ and $s_i = s_{i+1}$ .

Input format

The first line contains the string $s$ ( $2 \le n \le 10^5$ ). The second line contains $m$ ( $1 \le m \le 10^5$ ). The next $m$ lines contain $l$ and $r$ ( $1 \le l < r \le n$ ).

Output format

For every query print one number on a separate line.

Examples

Input

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

Output

Input

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

Output

Note

Let $c_i = 1$ if $s_i = s_{i+1}$ and $0$ otherwise. The answer is $c_l + \ldots + c_{r-1}$ , that is $p_{r-1} - p_{l-1}$ with prefix sums of $c$ . Watch the indices: $i = r$ is not counted.

In the first query of the second example (#..) only $s_2 = s_3$ works — the answer is $1$ .

Source: Codeforces, problem 313B.