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.io.*;
import java.util.*;

public class H {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		S = rd.readLine();
		char[] ch = new char[S.length()];
		for(int i=0; i<ch.length; i++) ch[i] = S.charAt(ch.length-1-i);
		R = new String(ch);
		hashAll();
		precalc();
		Q = Integer.parseInt(rd.readLine());
		StringTokenizer st;
		ty();
		for(int i=0; i<Q; i++){
			st = new StringTokenizer(rd.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			pw.println(ans[a-1][b-1]);
		}
		pw.flush();
	}
	
	static void hashAll(){
		H1 = new int[5001];
		H2 = new int[5002];
		int f = (int) (S.charAt(0)-'a');
		int f1 = (int) (R.charAt(0)-'a');
		H1[0] = f;
		H2[0] = f1;
		for(int i=1; i<S.length(); i++){
			int cur = (int) (S.charAt(i)-'a'), cur1 = (int) (R.charAt(i)-'a');
			H1[i] = (int) ( (mult*H1[i-1] + cur)%P );
			H2[i] = (int) ( (mult*H2[i-1] + cur1)%P );
		}
	}
	
	static int[] H1, H2;
	
	static long mult = 101, P = 1000000007;
	
	static void ty(){
		for(int a=S.length()-1; a>=0; a--){
			for(int b=a; b<=S.length()-1; b++){
				if(a==b) ans[a][b] = 1;
				else if(b==a+1) ans[a][b] = (S.charAt(a)==S.charAt(b)? 3: 2);
				else{
					if(a<=b) ans[a][b] = ans[a+1][b] + ans[a][b-1] - ans[a+1][b-1] + (isPalin(a, b)? 1: 0);
				}
			}
		}
	}
	
	static boolean isPalin(int x, int y){
		if(x==y) return true;
		int hash1 = x==0? H1[y]: (int) ((P + H1[y] - (pow[y-x+1]*H1[x-1])%P)%P);
		int y1 = S.length()-1-x;
		int x1 = S.length()-1-y;
		int hash2 = x1==0? H2[y1]: (int) ((P+H2[y1] - (x1==0? 0: (pow[y1-x1+1]*H2[x1-1])%P))%P);
		return hash1==hash2;
	}
	
	static long[] pow;
	
	static void precalc(){
		pow = new long[5002];
		pow[0] = 1L;
		for(int i=1; i<pow.length; i++) pow[i] = (mult*pow[i-1])%P;
	}
	
	
	static int[][] ans = new int[5001][5001];
	
	static int Q;
	static String S, R;
	
}
