You've got a string s = s1s2... s|s| of length |s|, consisting of lowercase English letters. There also are q queries, each query is described by two integers li, ri (1 ≤ li ≤ ri ≤ |s|). The answer to the query is the number of substrings of string s[li... ri], which are palindromes.

String s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s1s2... s|s|.

String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t1t2... t|t| = t|t|t|t| - 1... t1.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106) — the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the description of the i-th query.

It is guaranteed that the given string consists only of lowercase English letters.

Output

Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Examples

Input

caaaba
5
1 1
1 4
2 3
4 6
4 5


Output

1
7
3
4
2

Note

Consider the fourth query in the first test case. String s[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».
import java.util.*;
import java.io.*;
public class H {
	int[][] pal;
	public boolean palindrome(char[] c, int x, int y){
		for(int i = 0; i <= y-x; i++){
			if( c[i+x] != c[y-i] ){
				return false;
			}
		}
		return true;
	}
	public void pal(char[] c, int x){
		int mod = 1000000007;
		int id = x-1;
		int mul = 137;
		long temp = 1;
		long d = 0;
		long e = 0;
		int count = 0;
		while( id >= 0 ){
			d *= mul;
			d += c[id];
			e += temp*c[id];	
			d %= mod;
			e %= mod;
			if( d == e ){
				count++;
			}
			pal[x][id+1] = count;
			if( id+1 < x ){
				pal[x][id+1] += pal[x-1][id+1];
			}
			temp *= mul;
			temp %= mod;
			id--;
		}
	}
	public void solve() throws IOException {
		char[] str = nextToken().toCharArray();
		pal = new int[str.length+1][];
		pal[0] = new int[1];
		pal[1] = new int[2];
		pal[1][1] = 1;
		for(int i = 1; i < str.length; i++){
			pal[i+1] = new int[i+2];
			pal(str, i+1);		
		}
	/*	for(int[] x : pal){
			for(int y : x){
				writer.print(y + " ");
			}
			writer.println();
		}*/
		int q = nextInt();
		for(int i = 0; i < q; i++){
			int a = nextInt();
			int b = nextInt();
			writer.println(pal[b][a]);
		}
	}

	public static void main(String[] args) throws IOException {
		new H().run();
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;

	public void run() throws IOException {
		try {
			reader = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			writer = new PrintWriter(System.out);
			solve();
			reader.close();
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	public String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

}
