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.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Codeforces {

    private static Print writer;

    private static Scan reader;

    static class Scan {
        private byte[] buf = new byte[1024];  //Buffer of Bytes
        private int index;
        private InputStream in;
        private int total;

        public Scan() throws IOException {
            in = System.in;
        }

        int next() throws IOException {  //Scan method used to scan buf
            if (total < 0)
                throw new InputMismatchException();
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0)
                    return -1;
            }
            return buf[index++];
        }

        int ni() throws IOException {
            int integer = 0;
            int n = next();
            while (isWhiteSpace(n))   //Removing startPointing whitespaces
                n = next();
            int neg = 1;
            if (n == '-') {           //If Negative Sign encounters
                neg = -1;
                n = next();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = next();
                } else throw new InputMismatchException();
            }
            return neg * integer;
        }

        long nl() throws IOException {
            long integer = 0;
            int n = next();
            while (isWhiteSpace(n))   //Removing startPointing whitespaces
                n = next();
            int neg = 1;
            if (n == '-') {           //If Negative Sign encounters
                neg = -1;
                n = next();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = next();
                } else throw new InputMismatchException();
            }
            return neg * integer;
        }

        String line() throws IOException {
            StringBuilder sb = new StringBuilder();
            int n = next();
            while (isWhiteSpace(n)) n = next();
            while (!isNewLine(n)) {
                sb.append((char) n);
                n = next();
            }
            return sb.toString();
        }

        private boolean isNewLine(int n) {
            return n == '\n' || n == '\r' || n == -1;
        }

        private boolean isWhiteSpace(int n) {
            return n == ' ' || isNewLine(n) || n == '\t';
        }

        int[] nia(int n) throws Exception {
            if (n < 0) throw new Exception("Array size should be non negative");
            int[] array = new int[n];
            for (int i = 0; i < n; i++) array[i] = ni();
            return array;
        }

        int[][] n2dia(int r, int c) throws Exception {
            if (r < 0 || c < 0) throw new Exception("Array size should be non negative");
            int[][] array = new int[r][c];
            for (int i = 0; i < r; i++) array[i] = nia(c);
            return array;
        }

        long[] nla(int n) throws Exception {
            if (n < 0) throw new Exception("Array size should be non negative");
            long[] array = new long[n];
            for (int i = 0; i < n; i++) array[i] = nl();
            return array;
        }

        float[] nfa(int n) throws Exception {
            if (n < 0) throw new Exception("Array size should be non negative");
            float[] array = new float[n];
            for (int i = 0; i < n; i++) array[i] = nl();
            return array;
        }

        double[] nda(int n) throws Exception {
            if (n < 0) throw new Exception("Array size should be non negative");
            double[] array = new double[n];
            for (int i = 0; i < n; i++) array[i] = nl();
            return array;
        }
    }

    static class Print {
        private final BufferedWriter bw;


        Print() {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        <T> void print(T str) {
            try {
                bw.append(str.toString());
            } catch (IOException e) {
                System.out.println(e.toString());
            }
        }

        void println() {
            print("\n");
        }

        <T> void println(T str) {
            print(str + "\n");
        }

        void flush() throws IOException {
            bw.flush();
        }

        void close() {
            try {
                bw.close();
            } catch (IOException e) {
                System.out.println(e.toString());
            }
        }
    }

    public static void main (String[] args) throws Exception {
        long startPointTime = System.currentTimeMillis();
        reader = new Scan();
        writer = new Print();
        main2();
        long endTime = System.currentTimeMillis();
        float totalProgramTime = endTime - startPointTime;
        if (args.length > 0 && args[0].equals("time"))
            writer.print("Execution time is " + totalProgramTime + " (" + (totalProgramTime / 1000) + "s)");
        writer.close();
    }

    static class DisjointSet {
        int[] arr;
        int[] size;

        DisjointSet(int n) {
            arr = new int[n + 1];
            size = new int[n + 1];
            size[0] = 0;
            makeSet();
        }
        void makeSet() {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = i;
                size[i] = 1;
            }
        }
        void union(int i, int j) {
            j = find(j);
            i = find(i);
            if (i == j) return;
            arr[j] = arr[i];
            size[i] += size[j];
        }
        int find(int i) {
            if (arr[i] != i) {
                arr[i] = find(arr[i]);
            }
            return arr[i];
        }
        int getSize(int i) {
            i = find(i);
            return size[i];
        }
        public String toString() {
            return Arrays.toString(arr);
        }
    }

    static long MOD = 1_000_000_007L;
    static void main2 () throws Exception {
        String in = reader.line();
        int[] pre = new int[in.length()];
        pre[0] = 0;
        for (int i = 1; i < pre.length; i++) {
            if (in.charAt(i) == in.charAt(i - 1)) {
                pre[i] = 1 + pre[i - 1];
            } else {
                pre[i] = pre[i - 1];
            }
        }
        // writer.println(Arrays.toString(pre));
        int m = reader.ni();
        while (m-- > 0) {
            int l = reader.ni() - 1;
            int r = reader.ni() - 1;
            writer.println(pre[r] - pre[l]);
        }
    }
    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
}