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.* ;

public class Solution {
    public static void main(String[] args)throws IOException{
        IO io = new IO() ;
        String ip = io.getStringArray(1).get(0) ;
        int m = io.getIntegerArray(1).get(0) ;
        ArrayList<IO.Pair<Integer>> pairs = io.getIntegerPairArray(m) ;
        int[] preSum = new int[ip.length()] ;

        preSum[0] = ip.charAt(0) == ip.charAt(1) ? 1: 0 ;
        for(int i = 1 ; i < ip.length() - 1 ; i++){
            preSum[i] = preSum[i - 1] ;
            if(ip.charAt(i) == ip.charAt(i + 1))
                preSum[i]++ ;
        }
        preSum[ip.length() - 1] = preSum[ip.length() - 2] ;
        for(IO.Pair<Integer> p: pairs){
            int l = p.a - 1, h = p.b - 2 ;
            System.out.println(preSum[h] - (l == 0 ? 0: preSum[l - 1]));
        }
    }

    public static long getMin(int n, int m){
        int numEach = n / m, rem = n % m ;
        long res ;

        res = rem*(((long)numEach+1) * numEach) / 2 ;
        res += (m - rem)*(((long)numEach) * (numEach - 1)) / 2 ;
        return res ;
    }

    public static long getMax(int n, int m){
        long res = 0 ;
        int largest = n - (m - 1) ;

        res = (((long)largest)*(largest - 1)) / 2 ;
        return res ;
    }
}

class Utils{
    static class IndexedElement<T>{
        int idx;
        T val ;
        public IndexedElement(int idx, T val){
            this.idx = idx ;
            this.val = val ;
        }
    }
    public static <T> ArrayList<IndexedElement<T>> getIndexedArray(ArrayList<T> ip){
        ArrayList<IndexedElement<T>> op = new ArrayList<>() ;
        for(int i = 0 ; i < ip.size() ; i++){
            op.add(new IndexedElement<>(i, ip.get(i))) ;
        }
        return op ;
    }

    public static <T extends Comparable<T>> int getMax(T ... arr){
        if(arr.length == 0)
            return -1 ;
        int idx = 0 ;
        for(int i = 1 ; i < arr.length ; i++){
            if(arr[idx].compareTo(arr[i]) > 0)
                idx = i ;
        }
        return idx ;
    }
}

class IO{
    private BufferedReader br = null ;

    public IO(){
        this.br = new BufferedReader(new InputStreamReader(System.in)) ;
    }

    public ArrayList<Integer> getIntegerArray(int n)throws IOException{
        ArrayList<Integer> arr = new ArrayList<>() ;
        StringTokenizer st = new StringTokenizer(br.readLine()) ;

        while(st.hasMoreTokens()){
            arr.add(Integer.parseInt(st.nextToken())) ;
            if(arr.size() == n)
                break ;
        }

        return arr ;
    }

    public ArrayList<Long> getLongArray(int n)throws IOException{
        ArrayList<Long> arr = new ArrayList<>() ;
        StringTokenizer st = new StringTokenizer(br.readLine()) ;

        while(st.hasMoreTokens()){
            arr.add(Long.parseLong(st.nextToken())) ;
        }

        return arr ;
    }

    public ArrayList<Double> getDoubleArray(int n)throws IOException{
        ArrayList<Double> arr = new ArrayList<>() ;
        StringTokenizer st = new StringTokenizer(br.readLine()) ;

        while(st.hasMoreTokens()){
            arr.add(Double.parseDouble(st.nextToken())) ;
        }

        return arr ;
    }

    public ArrayList<String> getStringArray(int n)throws IOException{
        ArrayList<String> arr = new ArrayList<>() ;
        StringTokenizer st = new StringTokenizer(br.readLine()) ;

        while(st.hasMoreTokens()){
            arr.add(st.nextToken()) ;
        }

        return arr ;
    }

    static class Pair<T>{
        T a, b ;
        public Pair(T a, T b){
            this.a = a ;
            this.b = b ;
        }
    }
    public ArrayList<Pair<Integer>> getIntegerPairArray(int n)throws IOException{
        ArrayList<Pair<Integer>> pairs = new ArrayList<>() ;
        for(int i = 0 ; i < n ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()) ;
            pairs.add(new Pair<>(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))) ;
        }
        return pairs ;
    }
}