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:
//package codeForcesPractice;

import java.util.Scanner;

public class IlyaAndQueries {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder ans = new StringBuilder();
		String workP = sc.next();
		int size = workP.length();
		int q = sc.nextInt();
		int dp[] = new int[size];
		for (int i = 0; i < size - 1; i++) {
			if (workP.charAt(i + 1) == workP.charAt(i)) {
				dp[i] = 1;
			}
		}
		SegmentTree st = new SegmentTree(dp, size);
		for (int i = 0; i < q; i++) {
			int append = st.getSum(size, sc.nextInt() - 1, sc.nextInt() - 2);
			ans.append(append + "\n");
		}
		System.out.println(ans);
	}
}

class SegmentTree {
	int st[];

	SegmentTree(int arr[], int n) {

		int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));

		int max_size = 2 * (int) Math.pow(2, x) - 1;

		st = new int[max_size];

		constructSTUtil(arr, 0, n - 1, 0);
	}

	// A utility function to get the middle index from corner indexes.
	int getMid(int s, int e) {
		return s + (e - s) / 2;
	}

	int getSumUtil(int ss, int se, int qs, int qe, int si) {
		// If segment of this node is a part of given range, then return
		// the sum of the segment
		if (qs <= ss && qe >= se)
			return st[si];

		// If segment of this node is outside the given range
		if (se < qs || ss > qe)
			return 0;

		// If a part of this segment overlaps with the given range
		int mid = getMid(ss, se);
		return getSumUtil(ss, mid, qs, qe, 2 * si + 1) + getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
	}

	int getSum(int n, int qs, int qe) {
		// Check for erroneous input values
		if (qs < 0 || qe > n - 1) {
			System.out.println("Invalid Input");
			return -1;
		} else if (qs > qe) {
			return getSumUtil(0, n - 1, qs, qs, 0);
		}
		return getSumUtil(0, n - 1, qs, qe, 0);
	}

	int constructSTUtil(int arr[], int ss, int se, int si) {

		if (ss == se) {
			st[si] = arr[ss];
			return arr[ss];
		}

		int mid = getMid(ss, se);
		st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, si * 2 + 2);
		return st[si];
	}

}