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.Arrays;
import java.util.StringTokenizer;


public class CFR {
    static int[] adjList[];
    static int[] size;
    static FenwickTree ft;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        char[] s = sc.next().toCharArray();
        int q = sc.nextInt();
        int n = s.length;
        Query[] qs = new Query[q];
        for (int i = 0; i < q; i++)
            qs[i] = new Query(sc.nextInt(), sc.nextInt(), i);
        Arrays.sort(qs);
        ft = new FenwickTree(n);
        manacher(s);
        int L = 1;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            while (L < qs[i].l) {
                for (int j = 0; j < size[L-1]; j++)
                    ft.updatepoint(adjList[L-1][j], -1);
                L++;
            }
            ans[qs[i].i] = ft.rsq(qs[i].l, qs[i].r);
        }
        for (int x : ans)
            out.println(x);
        out.flush();
        out.close();
    }

    static void manacher(char[] s) {
        int n = s.length, d1[] = new int[n], d2[] = new int[n];

        for (int i = 0, l = 0, r = -1; i < n; ++i) {
            int k = i > r ? 1 : Math.min(r - i + 1, d1[l + r - i]);
            while (i + k < n && i - k >= 0 && s[i + k] == s[i - k])
                ++k;
            d1[i] = k--;
            if (i + k > r) {
                l = i - k;
                r = i + k;
            }
        }

        for (int i = 0, l = 0, r = -1; i < n; ++i) {
            int k = i > r ? 0 : Math.min(r - i + 1, d2[l + r - i + 1]);
            while (i + k < n && i - k - 1 >= 0 && s[i + k] == s[i - k - 1])
                ++k;
            d2[i] = k--;
            if (i + k > r) {
                l = i - k - 1;
                r = i + k;
            }
        }
        adjList = new int[n][n];
        size = new int[n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < d1[i]; j++) {
                int left = i - j;
                int right = i + j;
                adjList[left][size[left]++] = (right + 1);
                ft.updatepoint(right+1, 1);
            }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d2[i]; j++) {
                int left = i - 1 - j;
                int right = i + j;
                adjList[left][size[left]++] = (right + 1);
                ft.updatepoint(right+1, 1);
            }
        }

    }

    static class FenwickTree {
        int n;
        int[] ft;

        public FenwickTree(int n) {
            this.n = n;
            ft = new int[n + 1];
        }

        int rsq(int b) {
            int sum = 0;
            while (b > 0) {
                sum += ft[b];
                b -= b & -b;
            }
            return sum;
        }

        int rsq(int i, int j) {
            return rsq(j) - rsq(i - 1);
        }

        void updatepoint(int k, int val) {
            while (k <= n) {
                ft[k] += val;
                k += k & -k;
            }
        }
    }

    static class Query implements Comparable<Query> {
        int l, r, i;

        public Query(int l, int r, int i) {
            this.l = l;
            this.r = r;
            this.i = i;
        }

        @Override
        public int compareTo(Query o) {
            return (l == o.l) ? r - o.r : l - o.l;
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }

        public Scanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

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

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }
    }
}