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

public class Main {
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static long MOD = (long) (1e9 + 7);
    //    static int MOD = 998244353;
    static long MOD2 = MOD * MOD;
    static FastReader sc = new FastReader();
    static int pInf = Integer.MAX_VALUE;
    static int nInf = Integer.MIN_VALUE;
    static long ded = (long)(1e17)+9;
    public static void main(String[] args) throws Exception {
        int test = 1;
//        test = sc.nextInt();
        for (int i = 1; i <= test; i++){
//            out.print("Case #"+i+": ");
            solve();
        }
        out.flush();
        out.close();
    }
    static char[] c;
    static long[][] dp;
    static boolean[][] isPal;
    static void solve()throws Exception{
        char[] c = sc.next().toCharArray();
        int n = c.length;
        dp = new long[n+1][n+1];
        isPal = new boolean[n][n];
        for(int i = 0; i < n; i++){
            isPal[i][i] = true;
        }
        //Odd palindrome
        for(int radius = 1; ((2*radius)+1)<= n; radius++){
            for(int center = radius; center+radius<n; center++){
                if (!isPal[center-radius+1][center+radius-1])continue;
                if (c[center-radius]==c[center+radius]){
                    isPal[center-radius][center+radius] = true;
                }
            }
        }
        //Even palindrome
        for (int radius=0; radius*2<=n; radius++) {
            for (int lCenter=radius; lCenter+1+radius<n; lCenter++) {
                if (!(radius==0||isPal[lCenter-radius+1][lCenter+1+radius-1])) continue;
                if (c[lCenter-radius]==c[lCenter+1+radius])
                    isPal[lCenter-radius][lCenter+1+radius]=true;
            }
        }
//        for(int i= 0; i < n; i++){
//            out.println(Arrays.toString(isPal[i]));
//        }
        dp[0][0] = 0;
        for(int i= 1; i <= n; i++){
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (isPal[i-1][j-1] ? 1 : 0);
            }
        }
//        for(int i= 0; i <= n; i++){
//            out.println(Arrays.toString(dp[i]));
//        }
        int q = sc.nextInt();
        while (q-->0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            out.println(dp[r][r]+dp[l-1][l-1]-dp[r][l-1]-dp[l-1][r]);
        }
    }
    static boolean isPalindrome(String s){
        int n = s.length();
        for(int l = 0,r = n-1; l < r; l++,r--){
            if(s.charAt(l)!=s.charAt(r)){
                return false;
            }
        }
        return true;
    }
    private static int[] zValues(char[] s) {
        int n=s.length;
        int[] z=new int[n];
        z[0]=s.length;
        int l=0, r=0;
        for (int i=1; i<n; i++) {
            if (i>r) {
                l=r=i;
                while (r<n&&s[r]==s[r-i])
                    r++;

                z[i]=r-l;
                r--;
            }
            else {
                int k=i-l;
                if (z[k]<r-i+1) {
                    z[i]=z[k];
                }
                else {
                    l=i;
                    while (r<n&&s[r-l]==s[r])
                        r++;
                    z[i]=r-l;
                    r--;
                }
            }
        }
        return z;
    }
    static class Pair implements Comparable<Pair> {
        int x;
        int y;
        int idx;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Pair o) {
            return -1*(this.x-o.x);
        }
    }
    public static long mul(long a, long b) {
        return ((a % MOD) * (b % MOD)) % MOD;
    }
    public static long add(long a, long b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    public static long c2(long n) {
        if ((n & 1) == 0) {
            return mul(n / 2, n - 1);
        } else {
            return mul(n, (n - 1) / 2);
        }
    }
    //Shuffle Sort
    static final Random random = new Random();
    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n); int temp= a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }
    //Brian Kernighans Algorithm
    static long countSetBits(long n) {
        if (n == 0) return 0;
        return 1 + countSetBits(n & (n - 1));
    }
    //Euclidean Algorithm
    static long gcd(long A, long B) {
        if (B == 0) return A;
        return gcd(B, A % B);
    }
    //Modular Exponentiation
    static long fastExpo(long x, long n) {
        if (n == 0) return 1;
        if ((n & 1) == 0) return fastExpo((x * x) % MOD, n / 2) % MOD;
        return ((x % MOD) * fastExpo((x * x) % MOD, (n - 1) / 2)) % MOD;
    }
    //AKS Algorithm
    static boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i <= Math.sqrt(n); i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }
    public static long modinv(long x) {
        return modpow(x, MOD - 2);
    }
    public static long modpow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        long x = modpow(a, b / 2);
        x = (x * x) % MOD;
        if (b % 2 == 1) {
            return (x * a) % MOD;
        }
        return x;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}