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.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

import static java.lang.Math.*;

public class Main {

	public static void solve(FastScanner fscan, BufferedWriter bw) throws IOException
	{
		char seq[] = fscan.nextString().toCharArray();
		int sames[] = new int[seq.length+1];

		if(seq.length > 1 && seq[0] == seq[1])
		{
			sames[1] = 1;
		}
		for (int i = 1; i < seq.length - 1; i++) 
		{
			sames[i+1] = sames[i];
			if(seq[i] == seq[i+1])
			{
				sames[i+1] += 1;
			}
		}
		if(seq.length > 1)
		{
			sames[seq.length] = sames[seq.length - 1]; 
		}
		int q = fscan.nextInt();
		for (int i = 0; i < q; i++) 
		{
			int l = fscan.nextInt(),
				r = fscan.nextInt();
			
			bw.append(String.valueOf(sames[r-1] - sames[l-1]) + "\n");
		}
	}

	/**************** ENTER HERE   ********************/
	public static void main(String[] args) throws Exception {
		
		if(args.length != 0){
			test();
			return;
		}
		
		FastScanner fscan = new FastScanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		solve(fscan,bw);
		bw.close();
	}
	
	/****   Test Static test cases      **/
	public static void test() throws IOException{
		String testcase[] = new String[]{};
		String answer[] = new String[]{};
		
		for (int i = 0; i < testcase.length; i++) {
			ByteArrayOutputStream result = new ByteArrayOutputStream();
			FastScanner fscan = new FastScanner(new ByteArrayInputStream(testcase[i].getBytes()));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(result));
			
			solve(fscan, bw);
			
			String r = new String(result.toByteArray());
			if(! r.equals(answer[i])){
				String q = testcase[i];
				String a = answer[i];

				System.err.println("Wrong Answer on test:"+(i+1));
				System.err.println("Q:"+q);
				System.err.println("A:"+a);
				System.err.println("R:"+r);
			}
			
		}

	}
}





class FastScanner {
	InputStream is;
	byte buff[] = new byte[1024];
	int currentChar = -1;
	int buffChars = 0;

	public FastScanner(InputStream inputStream) {
		is = inputStream;
	}

	public boolean hasNext() throws IOException {
		return currentChar == -1 || buffChars > 0;
	}

	public char nextChar() throws IOException {
		// if we already have that next char read, just return else input
		if (currentChar == -1 || currentChar >= buffChars) {
			currentChar = 0;
			buffChars = is.read(buff);
		}

		if (buffChars <= 0) {
			throw new RuntimeException("No char found...");
		}

		int ch;
		while (isSpace(ch = nextCharAsInt()))
			;
		return (char) ch;
	}

	public int nextCharAsInt() throws IOException {
		// if we already have that next char read, just return else input
		if (currentChar == -1 || currentChar >= buffChars) {
			currentChar = 0;
			buffChars = is.read(buff);
		}

		if (buffChars <= 0) {
			return -1;
		}
		return (char) buff[currentChar++];
	}

	public String nextLine() throws IOException {
		StringBuilder bldr = new StringBuilder();
		int ch;
		while (isLineEnd(ch = nextCharAsInt()))
			// ignore empty lines ???
			;

		do {
			bldr.append((char) ch);
		} while (!isLineEnd(ch = nextCharAsInt()));

		return bldr.toString();
	}

	public String nextString() throws IOException {
		StringBuilder bldr = new StringBuilder();
		int ch;
		while (isSpace(ch = nextCharAsInt()))
			;

		do {
			bldr.append((char) ch);
		} while (!isSpace(ch = nextCharAsInt()));

		return bldr.toString();
	}

	public int nextInt() throws IOException {
		// considering ASCII files--> 8 bit chars, unicode files has 16 bit
		// chars (byte1 then byte2)
		int result = 0;
		int sign = 1;
		int ch;
		while (isSpace(ch = nextCharAsInt()))
			;

		if (ch == '-') {
			sign = -1;
			ch = nextCharAsInt();
		}

		do {
			if (ch < '0' || ch > '9')
				throw new NumberFormatException("Found '" + ch
						+ "' while parsing for int.");

			result *= 10;
			result += ch - '0';
		} while (!isSpace(ch = nextCharAsInt()));

		return sign * result;
	}

	public long nextLong() throws IOException {
		// considering ASCII files--> 8 bit chars, unicode files has 16 bit
		// chars (byte1 then byte2)
		long result = 0;
		int sign = 1;
		int ch;
		while (isSpace(ch = nextCharAsInt()))
			;

		if (ch == '-') {
			sign = -1;
			ch = nextCharAsInt();
		}

		do {
			if (ch < '0' || ch > '9')
				throw new NumberFormatException("Found '" + ch
						+ "' while parsing for int.");

			result *= 10;
			result += ch - '0';
		} while (!isSpace(ch = nextCharAsInt()));

		return sign * result;
	}

	private boolean isLineEnd(int ch) {
		return ch == '\n' || ch == '\r' || ch == -1;
	}

	private boolean isSpace(int ch) {
		return ch == '\n' || ch == ' ' || ch == '\t' || ch == '\r' || ch == -1;
	}

	public void close() throws IOException {
		is.close();
	}
}