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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author ahmadla
 */

public class rt {

    /**
     * @param args the command line arguments
     */
    static long sum=0;
    public static void fun(long a[],long i,long c,long val,String s){
  
   
    }
    public static void main(String[] args) {
        // TODO code application logic here
        
        Scanner in =new Scanner (System.in);
       String st= in.next();
    
      long s[]=new long [st.length()+1];
      long sum0=0;
         long csum[]=new long [s.length]; 
          int count=0;
        for (int i=1 ;i<s.length;i++) {
      
            
            csum[i]=count;
               if(i<st.length())
        if(st.charAt(i-1)==st.charAt(i))
          count++;}
    long t=in.nextLong();
      
  
        int r=0,l=0,c=0;

        for (long i = 0; i < t; i++)
        {
       l=in.nextInt();
        r=in.nextInt();
      
           System.out.println(csum[r]-csum[l]);  
           
        }
    }
    
}