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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main313B {
    private static String str;
    private static int n;
    private static int t[];
    public static void main(String[] args) {
        try (BufferedReader rd = new BufferedReader(new InputStreamReader(System.in))) {

            str = rd.readLine();
            n = str.length();
            t = new int[ n* 4 ];

            initTree(1,0,n - 1);

            int k  = Integer.parseInt(rd.readLine());
            for (int i = 0; i < k; i++) {
                String line = rd.readLine();
                String[] parts = line.split("\\s+");
                int l = Integer.parseInt(parts[0]) - 1;
                int r = Integer.parseInt(parts[1]) - 2;
                System.out.println(get(1,l,r,0,n-1));
            }
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    private static int get(int v, int l, int r,int tl,int tr) {
        if( r < l ) {
            return 0;
        }
        if(l == tl && r == tr) {
            return t[v];
        }
        int m = tl + (tr-tl)/2;
        return get(2*v,l,Math.min(m,r),tl,m) + get(2*v+1,Math.max(l,m+1),r,m+1,tr);
    }

    private static void initTree(int v, int l, int r) {
        if( l == r ) {
            if( l != n-1 && str.charAt(l) == str.charAt(l+1) ) {
                t[v] = 1;
            }

            //System.out.println("L " + l + " = "+t[v]);

            return;
        }
        int m = l + (r-l)/2;
        initTree(2*v,l,m);
        initTree(2*v+1,m+1,r);
        t[v] = t[2*v] + t[v*2 + 1];
        //System.out.println(String.format("S %d %d = ",l,r)+t[v]);
    }
}