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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskH solver = new TaskH();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskH {
        char[] s;
        boolean[][] pal;
        int[][] pref;
        int[][] sum;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            s = in.next().toCharArray();
            pal = new boolean[s.length + 1][s.length + 1];
            pref = new int[s.length + 1][s.length + 1];
            sum = new int[s.length + 1][s.length + 1];
            palCalc();
            build();
            int q = in.nextInt();
            for (int i = 0; i < q; i++) {
                int l = in.nextInt();
                int r = in.nextInt();
                out.println(get(l, r));
            }
        }

        void palCalc() {
            for (int first = 1; first <= s.length; first++) {
                pal[first][first] = true;
                if (first < s.length && s[first - 1] == s[first]) {
                    pal[first][first + 1] = true;
                }
            }
            for (int len = 3; len <= s.length; len++) {
                for (int first = 1; first <= s.length; first++) {
                    int last = first + len - 1;
                    if (last > s.length) break;
                    if (pal[first + 1][last - 1] && s[first - 1] == s[last - 1]) {
                        pal[first][last] = true;
                    }
                }
            }
        }

        void build() {
            for (int i = 1; i <= s.length; i++) {
                for (int j = 1; j <= s.length; j++) {
                    pref[i][j] = pref[i][j - 1];
                    if (pal[i][j]) {
                        pref[i][j]++;
                    }
                }
            }
            for (int j = 1; j <= s.length; j++) {
                for (int i = 1; i <= s.length; i++) {
                    sum[i][j] = sum[i - 1][j] + pref[i][j];
                }
            }
        }

        int get(int min, int max) {
            int res = sum[max][max];
            res -= sum[min - 1][max];
            res -= sum[max][min - 1];
            res += sum[min - 1][min - 1];
            return res;
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String next() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

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

    }
}

