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.lang.reflect.Parameter;
import java.nio.charset.IllegalCharsetNameException;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        OutputStream outputStream = System.out;
        FastReader in = new FastReader();
        OutputWriter out = new OutputWriter(outputStream);
        Taska solver=  new Taska();
        solver.solve(in,out);
        out.close();
    }
}
class Taska{
    public void solve(FastReader in,OutputWriter out) {
        String s=in.nLine();
        int m=in.ni();
        int[] dp =new int[s.length()];
        dp[0]=0;
        for(int i=1; i<s.length();i++){
            if(s.charAt(i-1)==s.charAt(i)){
                dp[i]=dp[i-1]+1;
            }
            else {
                dp[i]=dp[i-1];
            }
        }
        while (m-->0){
            int l=in.ni()-1;
            int r=in.ni()-1;
            out.println(dp[r]-dp[l]);
        }
    }
}
class StringAlgorithm{
    public ArrayList<Integer> KMP(int[] text, int[] pat){
        ArrayList<Integer> res= new ArrayList<>();
        int[] lps=  lps(pat);
        int i=0;
        int j=0;
        int n=text.length;
        int m=pat.length;
        while(i<n){
            if(pat[j]==text[i]){
                i++;
                j++;
            }
            if(j==m){
                res.add(i-j);
                j=lps[j-1];
            }
            else if(i<n && pat[j]!=text[i]){
                if(j!=0){
                    j=lps[j-1];
                }
                else {
                    i=i+1;
                }
            }
        }
        return res;
    }
    public int[] lps(int[] pat){
        int[] ar= new int[pat.length];
        int len=0;
        int i=1;
        ar[0]=0;
        while(i<pat.length){
            if(pat[i]==pat[len]){
                len++;
                ar[i]=len;
                i++;
            }
            else{
                if(len!=0){
                    len= ar[len-1];
                }
                else {
                    ar[i]=0;
                    i++;
                }
            }
        }
        return ar;
    }
}
class FastReader {
    BufferedReader br;
    StringTokenizer st;

    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 ni() {
        return Integer.parseInt(next());
    }

    long nl() {
        return Long.parseLong(next());
    }

    double nd() {
        return Double.parseDouble(next());
    }

    String nLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;

    }

}
class OutputWriter extends PrintWriter {

    public OutputWriter(OutputStream outputStream) {
        super(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

}
class Pair<U, V> {
    final U first;
    final V second;
    Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Pair<?, ?> pair = (Pair<?, ?>) o;
        if (!first.equals(pair.first))
            return false;
        return second.equals(pair.second);
    }

    @Override
    public int hashCode() {
        return 31 * first.hashCode() + second.hashCode();
    }

    @Override
    public String toString() {
        return "(" + first + ", " + second + ")";
    }
    public static <U, V> Pair <U, V> of(U a, V b) {
        return new Pair<>(a, b);
    }

}