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

public class Main
{
    static Input in;
    static Output out;
    static final boolean OJ = System.getProperty("ONLINE_JUDGE") != null;

    public static void main(String[] args) throws IOException
    {
        in = new Input(OJ ? System.in : new FileInputStream("in.txt"));
        out = new Output(OJ ? System.out : new FileOutputStream("out.txt"));
        solve();
        out.close();
        System.exit(0);
    }

    private static void solve() throws IOException
    {
        String s = in.nextString();
        int[] A = new int[s.length() + 1];
        for (int i = 0; i < s.length() - 1; i++)
        {
            if (s.charAt(i) == s.charAt(i + 1)) A[i+2]++;
        }
        for (int i = 1; i < A.length; i++)
        {
            A[i] += A[i - 1];
        }
        int n = in.nextInt();
        for (int i = 0; i < n; i++)
        {
            int l = in.nextInt();
            int r = in.nextInt();
            if (r == l + 1)
            {
                out.println(s.charAt(l - 1) == s.charAt(r - 1) ? 1 : 0);
            }
            else out.println(A[r] - A[l]);
        }
    }


}

class Node
{
    int left, right, value;
    char c;

    public Node(int l, int r, char ch)
    {
        left = l; right = r; c = ch;
    }

    public void merge(Node leftChild, Node rightChild)
    {
        if (leftChild == null)
        {
            value = rightChild.value;
            c = rightChild.c;
        }
        else if (rightChild == null)
        {
            value = leftChild.value;
            c = leftChild.c;
        }
        else
        {
            c = rightChild.c;
            value = leftChild.value + rightChild.value;
            if (leftChild.c == rightChild.c) value++;
        }
    }
}

class SegmentTree
{
    int N;
    Node[] tree;

    public SegmentTree(char[] A)
    {
        N = A.length;
        int len = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) A.length) / Math.log(2.0)) + 1)));
        tree = new Node[len];
        build(1, 0, A.length - 1, A);
    }

    private void build(int node, int l, int r, char[] A)
    {
        if (l == r) // nodo hoja
        {
            tree[node] = new Node(l, r, A[l]);
            return;
        }
        int leftChild = node * 2, rightChild = leftChild + 1, mid = (l + r) / 2;
        build(leftChild, l, mid, A);      // calcular el valor del hijo izquierdo
        build(rightChild, mid + 1, r, A); // calcular el valor del hijo derecho
        tree[node] = new Node(l, r, tree[rightChild].c);
        tree[node].merge(tree[leftChild], tree[rightChild]);
    }

    private Node query(int node, int l, int r, int i, int j)
    {
        if (l >= i && r <= j) return tree[node]; // dentro del intervalo
        else if (j < l || i > r) return null;  // fuera del intervalo
        else // parcialmente dentro
        {
            int leftChild = 2 * node, rightChild = leftChild + 1, mid = (l + r) / 2;
            Node a = query(leftChild, l, mid, i, j);    // visitar hijo izquierdo
            Node b = query(rightChild, mid + 1, r, i, j); // visitar hijo derecho
            Node temp = new Node(-1, -1, '\0'); // combinamos la informacion
            temp.merge(a, b);
            return temp;
        }
    }

    public int query(int i, int j)
    {
        Node result = query(1, 0, N - 1, i, j);
        return result.value;
    }
}

class Input
{
    final int SIZE = 8192; //4096; 8192; 65536;
    InputStream in;
    byte[] buf = new byte[SIZE];
    int last, current, total;

    public Input(InputStream stream) throws IOException
    {
        in = stream; last = read();
    }

    int read() throws IOException
    {
        if (total == -1) return -1;
        if (current >= total)
        {
            current = 0; total = in.read(buf);
            if (total <= 0) return -1;
        }
        return buf[current++];
    }

    void advance() throws IOException
    {
        while (true)
        {
            if (last == -1) return;
            if (!isValidChar(last)) last = read();
            else break;
        }
    }

    boolean isValidChar(int c) { return c > 32 && c < 127; }

    public boolean endOfFile() throws IOException { advance(); return last == -1; }

    public String nextString() throws IOException
    {
        advance();
        if (last == -1) throw new EOFException();
        StringBuilder s = new StringBuilder();
        while (true)
        {
            s.appendCodePoint(last); last = read();
            if (!isValidChar(last)) break;
        }
        return s.toString();
    }

    public String nextLine() throws IOException
    {
        if (last == -1) throw new EOFException();
        StringBuilder s = new StringBuilder();
        while (last != '\n') last = read(); // go to end of current line
        last = read(); // go to next line
        while (true)
        {
            s.appendCodePoint(last); last = read();
            if (last == '\n' || last == '\r' || last == -1) break;
        }
        return s.toString();
    }

    public String nextLine(boolean ignoreIfEmpty) throws IOException
    {
        if (!ignoreIfEmpty) return nextLine();
        String s = nextLine();
        while (s.trim().length() == 0) s = nextLine();
        return s;
    }

    public int nextInt() throws IOException
    {
        advance();
        if (last == -1) throw new EOFException();
        int n = 0, s = 1;
        if (last == '-')
        {
            s = -1; last = read();
            if (last == -1) throw new EOFException();
        }
        while (true)
        {
            n = n * 10 + last - '0'; last = read();
            if (!isValidChar(last)) break;
        }
        return n * s;
    }

    public long nextLong() throws IOException
    {
        advance();
        if (last == -1) throw new EOFException();
        int s = 1;
        if (last == '-')
        {
            s = -1; last = read();
            if (last == -1) throw new EOFException();
        }
        long n = 0;
        while (true)
        {
            n = n * 10 + last - '0'; last = read();
            if (!isValidChar(last)) break;
        }
        return n * s;
    }

    public BigInteger nextBigInt() throws IOException { return new BigInteger(nextString()); }

    public char nextChar() throws IOException { advance(); return (char) last; }

    public double nextDouble() throws IOException
    {
        advance();
        if (last == -1) throw new EOFException();
        int s = 1;
        if (last == '-')
        {
            s = -1; last = read();
            if (last == -1) throw new EOFException();
        }
        double n = 0;
        while (true)
        {
            n = n * 10 + last - '0'; last = read();
            if (!isValidChar(last) || last == '.') break;
        }
        if (last == '.')
        {
            last = read();
            if (last == -1) throw new EOFException();
            double m = 1;
            while (true)
            {
                m = m / 10;
                n = n + (last - '0') * m; last = read();
                if (!isValidChar(last)) break;
            }
        }
        return n * s;
    }

    public BigDecimal nextBigDecimal() throws IOException { return new BigDecimal(nextString()); }

    public int[] nextIntArray(int len) throws IOException
    {
        int[] A = new int[len];
        for (int i = 0; i < len; i++) A[i] = nextInt();
        return A;
    }

    public long[] nextLongArray(int len) throws IOException
    {
        long[] A = new long[len];
        for (int i = 0; i < len; i++) A[i] = nextLong();
        return A;
    }

    public int[][] nextIntTable(int rows, int cols) throws IOException
    {
        int[][] T = new int[rows][];
        for (int i = 0; i < rows; i++) T[i] = nextIntArray(cols);
        return T;
    }
}

class Output
{
    final int SIZE = 4096; // 4096; 8192
    Writer out;
    char[] cb = new char[SIZE];
    int nChars = SIZE, nextChar = 0;
    char lineSeparator = '\n';

    public Output(OutputStream stream) { out = new OutputStreamWriter(stream); }

    void flushBuffer() throws IOException
    {
        if (nextChar == 0) return;
        out.write(cb, 0, nextChar);
        nextChar = 0;
    }

    void write(int c) throws IOException
    {
        if (nextChar >= nChars) flushBuffer();
        cb[nextChar++] = (char) c;
    }

    void write(String s, int off, int len) throws IOException
    {
        int b = off, t = off + len;
        while (b < t)
        {
            int a = nChars - nextChar, a1 = t - b;
            int d = a < a1 ? a : a1;
            s.getChars(b, b + d, cb, nextChar);
            b += d;
            nextChar += d;
            if (nextChar >= nChars) flushBuffer();
        }
    }

    void write(String s) throws IOException { write(s, 0, s.length()); }

    public void print(Object obj) throws IOException { write(String.valueOf(obj)); }

    public void println(Object obj) throws IOException
    {
        write(String.valueOf(obj));
        write(lineSeparator);
    }

    public void printf(String format, Object... obj) throws IOException { write(String.format(format, obj)); }

    public void printElements(Object... obj) throws IOException
    {
        for (int i = 0; i < obj.length; i++)
        {
            if (i > 0) print(" ");
            print(obj[i]);
        }
        print(lineSeparator);
    }

    public void close() throws IOException
    {
        flushBuffer();
        out.close();
    }
}