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 {
	
	public static void main(String[] args) throws Exception {
		
		FastScanner qwe = new FastScanner(System.in);
		
		char[] str = qwe.next().toCharArray();
		int q = qwe.nextInt();
		
		boolean[][] ispal = new boolean[str.length][str.length];
		int[][] dp = new int[str.length][str.length];
		
		for(int i =0; i < ispal.length; i++){
			ispal[i][i] = true;
			dp[i][i] = 1;
		}
		
		for(int len = 2; len <= ispal.length; len++){
			for(int start =0; start+len-1 < str.length; start++){
				ispal[start][start+len-1] = (start+1 > start + len -2 ? true : ispal[start+1][start+len-2]) && (str[start] == str[start+len-1]);
			}
		}
		
//		for(int i =0; i < ispal.length; i++)
//			for(int j =0;j < ispal.length; j++){
//				if(ispal[i][j]) System.out.println("pals: " + i + " " + j);
//			}
		
		for(int len = 2; len <= ispal.length; len++){
			for(int start =0; start+len-1 < str.length; start++){
				dp[start][start+len-1] = dp[start+1][start+len-1] + dp[start][start+len-2] - dp[start+1][start+len-2] + (ispal[start][start+len-1] ? 1 : 0);
			}
		}
		
		PrintWriter out = new PrintWriter(System.out);
		
		while(q-->0){
			out.println(dp[qwe.nextInt()-1][qwe.nextInt()-1]);
		}
		
		out.close();
		
	}
	
	
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in) throws Exception{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer(br.readLine().trim());
		}
		public int numTokens() throws Exception {
			if(!st.hasMoreTokens()){
				st = new StringTokenizer(br.readLine().trim());
				return numTokens();
			}
			return st.countTokens();
		}
		public String next() throws Exception {
			if(!st.hasMoreTokens()){
				st = new StringTokenizer(br.readLine().trim());
				return next();
			}
			return st.nextToken();
		}
		public double nextDouble() throws Exception{
			return Double.parseDouble(next());
		}
		public float nextFloat() throws Exception{
			return Float.parseFloat(next());
		}
		public long nextLong() throws Exception{
			return Long.parseLong(next());
		}
		public int nextInt() throws Exception{
			return Integer.parseInt(next());
		}
		public String nextLine() throws Exception{
			return br.readLine().trim();
		}
	}

}


	
	
	
