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.util.*;
	import java.io.*;
	import java.math.*;
	public class Codeforces {
		static char c[];
		public static void main(String[] args) throws Exception{
			//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String s = br.readLine();
			int dp[] = new int[s.length()+1];
			for(int i =1;i<dp.length;i++) {
				if(i<s.length() && s.charAt(i-1) == s.charAt(i)) {
					dp[i]++;
				}
				
			}
			for(int i =1;i<dp.length;i++)dp[i]+=dp[i-1];
			//System.out.println()
			int test = Integer.parseInt(br.readLine());
			while(test-->0) {
				String li[] = br.readLine().split(" ");
				int l = Integer.parseInt(li[0]);
				int r = Integer.parseInt(li[1])-1;
				if(l == 1)System.out.println(dp[r]);
				else System.out.println(dp[r]-dp[l-1]);
			}
		}
		public static void swap(int a,int b,int arr[]) {
			int t = arr[b];
			arr[b] = arr[a];
			arr[a] = t;
		}
		
	}
	/*****************************************Notes**********************************************
	
	1.Never use String.charAt for integers=> only works till 9 if integer val is 28,39,555
	charAt would pick only the first digit. Better use Integer.parseInt() to convert string to Integer
	
	2. even empty for loop can be used in certain cases.eg 'C - Pinkie Pie Eats Patty-cakes'. 
	ie.the check function of binary search. extra code but learnt some approach = SecondThreads implementation
	
	3. The two list subsequence method eg:D. Binary String To Subsequences (works only in the case of two characters)
	
	
	4. when there is a range that is computed there are case where index out of bounds might occur to keep
	the ranges proper use min max trick=> leftfarthest = max(0,computed) && rightFarthest = min(n-1,computed)
	
	***************************************************
	5.Think in reverse order eg:puzzle game
	bfs can be used to generate all possible combinations
	*******************
	6.carefully see the bounds for example incase of time see if its 12 hour or 24 hour
	**********************************
	plan the strategy before even coding and check for test cases if it workkkkkkkkkk
	
	sliding window technique: first and sec can be zero and is used especially if two numbers satify 
	a condition then the entire range satisfies(mainly on sorted arrays).whenever a variable is defaulted before
	execution think if that would change the result for certain cases and alter the initialization of res variable accordingly
	
	************
	in count of same value pick pairs of elements =>count/2;
	in count of different variables pick pairs => Math.min(count[a],count[b]);
	
	number divsible by k = k-elements[i]%k
	
	
	
	**************
	*/