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



import java.io.*;


 public class Codechef {


    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 

    public static void main(String[] args)throws java.lang.Exception {
        FastReader sc = new FastReader();
         StringBuffer sb = new StringBuffer();
       

        int t=1;
        while (t-->0) {

         String s=sc.next();
         int m=sc.nextInt();
         int n=s.length();
         int[] a=new int[n];
         a[0]=0;
         int c=0;
         for(int i=1;i<n;i++)
         {
             if(s.charAt(i-1)==s.charAt(i))
             c++; 
             
             a[i]=a[i-1]+c;
             c=0;
         }

        
         while(m-->0)
         {
             int l=sc.nextInt();
             int r=sc.nextInt();

             l--;
             r--;
              
                if((r-l)==1)
                {
                    if(s.charAt(l)==s.charAt(r))
                  sb.append(1).append("\n");
                  else
                  sb.append(0).append("\n");

                    continue;
                    
                }
        //   int f=a[r];
        //   if(l!=0)
        //   f--;

             sb.append(a[r]-a[l]).append("\n");
         }
            
            


           System.out.println(sb);
     
        }
        


        
    }

        
}