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

public class Template implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
    }

    class GraphBuilder {
        int n, m;
        int[] x, y;
        int index;
        int[] size;


        GraphBuilder(int n, int m) {
            this.n = n;
            this.m = m;
            x = new int[m];
            y = new int[m];
            size = new int[n];
        }

        void add(int u, int v) {
            x[index] = u;
            y[index] = v;
            size[u]++;
            size[v]++;
            index++;
        }

        int[][] build() {
            int[][] graph = new int[n][];
            for (int i = 0; i < n; i++) {
                graph[i] = new int[size[i]];
            }
            for (int i = index - 1; i >= 0; i--) {
                int u = x[i];
                int v = y[i];
                graph[u][--size[u]] = v;
                graph[v][--size[v]] = u;
            }
            return graph;
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    int[] readIntArray(int size) throws IOException {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long[] readLongArray(int size) throws IOException {
        long[] res = new long[size];
        for (int i = 0; i < size; i++) {
            res[i] = readLong();
        }
        return res;
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    <T> List<T>[] createGraphList(int size) {
        List<T>[] list = new List[size];
        for (int i = 0; i < size; i++) {
            list[i] = new ArrayList<>();
        }
        return list;
    }

    public static void main(String[] args) {
        new Template().run();
        // new Thread(null, new Template(), "", 1l * 200 * 1024 * 1024).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            if (System.getProperty("ONLINE_JUDGE") == null) {
                time();
                memory();
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    int n;
    int prime1, prime2;
    int mod1, mod2;
    int[] pow1, pow2;
    int[] h1, h2, rh1, rh2;

    void init(char[] s) {
        Random rnd = new Random();
        prime1 = BigInteger.valueOf(3000 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        prime2 = BigInteger.valueOf(4000 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        mod1 = BigInteger.valueOf((int) 1e9 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        mod2 = BigInteger.valueOf((int) 1e9 + (int) 1e6 + rnd.nextInt(500))
                .nextProbablePrime().intValue();
        n = s.length;
        pow1 = new int[n];
        pow2 = new int[n];
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i < n; i++) {
            pow1[i] = (int) ((long) pow1[i - 1] * prime1 % mod1);
            pow2[i] = (int) ((long) pow2[i - 1] * prime2 % mod2);
        }
        h1 = new int[n];
        h2 = new int[n];
        h1[0] = h2[0] = s[0];
        for (int i = 1; i < n; i++) {
            h1[i] = (int) ((h1[i - 1] + (long) pow1[i] * s[i]) % mod1);
            h2[i] = (int) ((h2[i - 1] + (long) pow2[i] * s[i]) % mod2);
        }
        rh1 = new int[n];
        rh2 = new int[n];
        rh1[n - 1] = rh2[n - 1] = s[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rh1[i] = (int) ((rh1[i + 1] + (long) pow1[n - 1 - i] * s[i]) % mod1);
            rh2[i] = (int) ((rh2[i + 1] + (long) pow2[n - 1 - i] * s[i]) % mod2);
        }
    }

    long getHash(int L, int R) {
        int hash1 = getHash(L, R, h1, pow1, mod1);
        int hash2 = getHash(L, R, h2, pow2, mod2);
        return ((long) hash1 << 32) | hash2;
    }

    long getRevHash(int L, int R) {
        int hash1 = getRevHash(L, R, rh1, pow1, mod1);
        int hash2 = getRevHash(L, R, rh2, pow2, mod2);
        return ((long) hash1 << 32) | hash2;
    }

    int getHash(int L, int R, int[] h, int[] pow, int mod) {
        int hash = h[R];
        if (L > 0)
            hash -= h[L - 1];
        if (hash < 0)
            hash += mod;
        return (int) ((long) hash * pow[n - R - 1] % mod);
    }

    int getRevHash(int L, int R, int[] rh, int[] pow, int mod) {
        int hash = rh[L];
        if (R < n - 1)
            hash -= rh[R + 1];
        if (hash < 0)
            hash += mod;
        return (int) ((long) hash * pow[L] % mod);
    }

    // s[L..R] = rev(s[L..R])
    boolean isPalindrome(int L, int R) {
        long hash = getHash(L, R);
        long revHash = getRevHash(L, R);
        return hash == revHash;
    }

    void solve() throws IOException {
        char[] s = readString().toCharArray();
        init(s);
        int[][] answer = new int[n][n];
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i; j >= 0; j--) {
                if (i - 1 >= 0) {
                    answer[j][i] = answer[j][i - 1];
                }
                if (isPalindrome(j, i)) count++;
                answer[j][i] += count;
            }
        }

        int q = readInt();
        while (q -- >0) {
            out.println(answer[readInt() - 1][readInt() - 1]);
        }
    }


}