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

public class BasicJava
{
   public static InputReader in = new InputReader( System.in );
   public static OutputWriter out = new OutputWriter( System.out );
   
   public static void main(String[] args)
   {
      String s = in.nextLine();
      int n = in.nextInt();
      int[] dp = new int [100010];
      int count=0;
      for (int i = 1; i < s.length(); i++)
         if (s.charAt(i-1) == s.charAt(i)) dp[i] = count++; else
            dp[i] = count;
      
      for (int i = 1; i <= n; i++) {
         
         int a = in.nextInt();
         int b = in.nextInt();
         
         out.println(dp[b]-dp[a]);
         
      }
      
      out.close();
   }
   
   static class InputReader
   {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
 
      public InputReader(InputStream stream)
      {
          this.stream = stream;
      }

      public InputReader(FileReader fileReader)
      {
         // TODO Auto-generated constructor stub
      }
 
      public int read()
       {
           if (numChars == -1)
               throw new InputMismatchException();
 
           if (curChar >= numChars)
           {
               curChar = 0;
               try
               {
                   numChars = stream.read(buf);
               } catch (IOException e)
               {
                   throw new InputMismatchException();
               }
               if (numChars <= 0)
                   return -1;
           }
 
           return buf[curChar++];
       }
 
       public int nextInt()
       {
           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 & 15;
 
               c = read();
           } while (!isSpaceChar(c));
 
           return res * sgn;
       }
 
       public int[] nextIntArray(int arraySize)
       {
           int array[] = new int[arraySize];
 
           for (int i = 0; i < arraySize; i++)
               array[i] = nextInt();
 
           return array;
       }
 
       public long nextLong()
       {
           int c = read();
 
           while (isSpaceChar(c))
               c = read();
 
           int sign = 1;
 
           if (c == '-')
           {
               sign = -1;
 
               c = read();
           }
 
           long result = 0;
 
           do
           {
               if (c < '0' || c > '9')
                   throw new InputMismatchException();
 
               result *= 10;
               result += c & 15;
 
               c = read();
           } while (!isSpaceChar(c));
 
           return result * sign;
       }
 
       public long[] nextLongArray(int arraySize)
       {
           long array[] = new long[arraySize];
 
           for (int i = 0; i < arraySize; i++)
               array[i] = nextLong();
 
           return array;
       }
 
       public float nextFloat() // problematic
       {
           float result, div;
           byte c;
 
           result = 0;
           div = 1;
           c = (byte) read();
 
           while (c <= ' ')
               c = (byte) read();
 
           boolean isNegative = (c == '-');
 
           if (isNegative)
               c = (byte) read();
 
           do
           {
               result = result * 10 + c - '0';
           } while ((c = (byte) read()) >= '0' && c <= '9');
 
           if (c == '.')
               while ((c = (byte) read()) >= '0' && c <= '9')
                   result += (c - '0') / (div *= 10);
 
           if (isNegative)
               return -result;
 
           return result;
       }
 
       public double nextDouble() // not completely accurate
       {
           double ret = 0, div = 1;
           byte c = (byte) read();
 
           while (c <= ' ')
               c = (byte) read();
 
           boolean neg = (c == '-');
 
           if (neg)
               c = (byte) read();
 
           do
           {
               ret = ret * 10 + c - '0';
           } while ((c = (byte) read()) >= '0' && c <= '9');
 
           if (c == '.')
               while ((c = (byte) read()) >= '0' && c <= '9')
                   ret += (c - '0') / (div *= 10);
 
           if (neg)
               return -ret;
 
           return ret;
       }
 
       public String next()
       {
           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 boolean isSpaceChar(int c)
       {
           return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
       }
 
       public String nextLine()
       {
           int c = read();
 
           StringBuilder result = new StringBuilder();
 
           do
           {
               result.appendCodePoint(c);
 
               c = read();
           } while (!isNewLine(c));
 
           return result.toString();
       }
 
       public boolean isNewLine(int c) { return c == '\n'; }
 
       public void close()
       {
           try
           {
               stream.close();
           } catch (IOException e)
           {
               e.printStackTrace();
           }
       }
 
   }
 
   static class OutputWriter
   {
       private PrintWriter writer;
 
       public OutputWriter(OutputStream stream)
       {
           writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                   stream)));
       }
 
       public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); }
 
       public void println(ArrayList a) { writer.println(a); }
 
       public void print(int x) { writer.print(x); }
 
       public void println(char x) { writer.println(x); }
 
       public void print(char x) { writer.print(x); }
 
       public void println(int array[], int size)
       {
           for (int i = 0; i < size; i++) println(array[i]);
       }
 
       public void print(int array[], int size)
       {
           for (int i = 0; i < size; i++)
               print(array[i] + " ");
       }
 
       public void println(long x) { writer.println(x); }
 
       public void print(long x) { writer.print(x); }
 
       public void println(long array[], int size)
       {
           for (int i = 0; i < size; i++)
               println(array[i]);
       }
 
       public void print(long array[], int size)
       {
           for (int i = 0; i < size; i++)
               print(array[i]);
       }
 
       public void println(float num) { writer.println(num); }
 
        
       public void print(float num) { writer.print(num); }
 
       public void println(double num) { writer.println(num); }
 
       public void print(double num) { writer.print(num); }
 
       public void println(String s) { writer.println(s); }
 
       public void print(String s) { writer.print(s); }
 
       public void println() { writer.println(); }
 
       public void printSpace() { writer.print(" "); }
 
       public void printf(String format, Object args) { writer.printf(format, args); }
 
       public void flush() { writer.flush(); }
 
       public void close() { writer.close(); }
 
   }
   
}