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 H245 {
 
	public static void main(String[] args) throws Exception{
 
		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		String input = bf.readLine().trim();
 		int q = Integer.parseInt(bf.readLine());
 		boolean [][] isPal = new boolean[input.length()][input.length()];
 		int[][] dp = new int[input.length()][input.length()];
 		for(int i = 0;i<input.length();i++){
 			isPal[i][i] = true;
 			if (i >=1)
 				isPal[i][i-1] = true;
 			dp[i][i] = 1;
 		}
 		for(int len = 2;len<=input.length();len++){
 			for(int start = 0;start<input.length()-len+1;start++){
 				isPal[start][start+len-1] = isPal[start+1][start+len-2] && (input.charAt(start) == input.charAt(start+len-1));
 				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);
 			}
 		}
 		
 		
 		for(int i = 0;i<q;i++){
 			StringTokenizer st = new StringTokenizer(bf.readLine());
 			int l = Integer.parseInt(st.nextToken());
 			int r = Integer.parseInt(st.nextToken());
 			out.println(dp[l-1][r-1]);
 		}
 		
 		
 		out.close();
 		
 		
 		
 		
	}
 
 }
	
 	
// 
////StringJoiner sj = new StringJoiner(" "); 
////sj.add(strings)
////sj.toString() gives string of those stuff w spaces or whatever that sequence is
//class BinaryIndexedTree 
//{  
//    // Max tree size 
//    final static int MAX = 1000005;      
//  
//    static int BITree[] = new int[MAX];     
//    /* n --> No. of elements present in input array.  
//    BITree[0..n] --> Array that represents Binary  
//                    Indexed Tree. 
//    arr[0..n-1] --> Input array for which prefix sum  
//                    is evaluated. */
//  
//    // Returns sum of arr[0..index]. This function  
//    // assumes that the array is preprocessed and  
//    // partial sums of array elements are stored  
//    // in BITree[]. 
//    int getSum(int index){ 
//        int sum = 0;
//        index = index + 1; 
//        while(index>0){ 
//            sum += BITree[index]; 
//            index -= index & (-index); 
//        } 
//        return sum; 
//    } 
//    public static void updateBIT(int n, int index, int val){ 
//        index = index + 1; 
//        while(index <= n){ 
//	        BITree[index] += val; 
//	        index += index & (-index); 
//        } 
//    } 
//    void constructBITree(int arr[], int n){ 
//        for(int i=1; i<=n; i++) 
//            BITree[i] = 0; 
//        for(int i = 0; i < n; i++) 
//            updateBIT(n, i, arr[i]); 
//    } 
//}
 	