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.util.*;
/**
 * @author Alvex - GoldenReam1503@gmail.com
 * Time: 10:04:13 AM
 * Date: Nov 19, 2015
 */
public class _313B_Ilya_and_Queries
{
    private static class Output
    {
        private final PrintWriter printer;
        public void printLine(Object...objects) 
        {
            print(objects);
            printer.println();
        }
        public void print(Object...objects) 
        {
            int i;
            for (i=0;i<objects.length;i++) 
            {
                if (i!=0)
                    printer.print(' ');
                printer.print(objects[i]);
            }
        }
        public Output(OutputStream outputStream)
        {
            printer= new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }
        public void flush()
        {
            printer.flush();
        }
        public void close()
        {
            printer.close();
        }
    }
    private static class Input
    {
        private InputStream stream;
        private byte Buffer[]=new byte[1024];
        private int curChar;
        private int numberChars;
        private SpaceCharFilter filter;
        public interface SpaceCharFilter 
        {
            public boolean isSpaceChar(int ch);
        }
        public Input(InputStream stream)
        {
            this.stream=stream;
        }
        public static boolean isWhitespace(int c) 
        {
            boolean flag=false;
            if(c==' '|| c=='\n' || c=='\r' || c=='\t' || c==-1)
                flag=true;
            return flag;
        }
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }
        public int read()
        {
            if (numberChars==-1)
                throw new InputMismatchException();
            if (curChar>=numberChars) 
            {
                curChar = 0;
                try 
                {
                    numberChars = stream.read(Buffer);
                } 
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                if (numberChars <= 0)
                    return -1;
            }
            return Buffer[curChar++];
        }
        public int readInt() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } 
            while (!isSpaceChar(c));
            return res * sgn;
        }
        public String readString() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            return res.toString();
        }
    }
    public static void main(String[] args)
    {   
        Input in=new Input(System.in);
        Output out=new Output(System.out);
        String s=in.readString();
        int n=s.length();
        int m=in.readInt();
        int i,k=0;
        int value[]=new int[n];
        for(i=1;i<n;i++)
        {
            if(s.charAt(i)==s.charAt(i-1))
                k++;
            value[i]=k;
        }
        for(i=0;i<m;i++)
        {
            int l,r;
            l=in.readInt();
            r=in.readInt();
            out.printLine(value[r-1]-value[l-1]);
        }
        out.flush();
        out.close();
    }
}