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 Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	   return Integer.parseInt(next());
    }

    Node []tree;
    int size = 0;

    int suff, n;

    final static int MAX = 100010;

    char []s;
    int [][]dp;

    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);

        s = next().toCharArray();
        init();
        n = s.length;

        dp = new int[n][n];
        for(int i = 0; i < n; ++i) {
            addLetter(i);
            int v = suff;
            while(v > 1) {
                int len = tree[v].len;
                dp[i - len + 1][i]++;
                v = tree[v].sufflink;
            }
        }

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if (i > 0) dp[i][j] += dp[i-1][j];
                if (j > 0) dp[i][j] += dp[i][j-1];
                if (i > 0 && j > 0) dp[i][j] -= dp[i-1][j-1];
            }
        }

        // for(int i = 0; i < n; ++i) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }

        int q = nextInt();
        while(q-->0) {
            int l = nextInt() - 1, r = nextInt() - 1;
            int ret = dp[r][r];
            if (l > 0) {
                ret -= dp[l-1][r];  
                ret -= dp[r][l-1];
                ret += dp[l-1][l-1];
            }
            out.println(ret);
        }

        out.close();
    }

    private boolean addLetter(int pos) {
        int cur = suff, curlen = 0;
        int let = s[pos] - 'a';

        while(true) {
            curlen = tree[cur].len;
            if (pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) {
                break;
            }
            cur = tree[cur].sufflink;
        }

        if (tree[cur].next[let] != -1) {
            suff = tree[cur].next[let];
            return false;
        }

        int v = size++;
        suff = v;
        tree[v] = new Node(tree[cur].len + 2);
        // tree[v].num = 1;
        tree[cur].next[let] = v;

        if (tree[v].len == 1) {
            tree[v].sufflink = 1;
            return true;
        }

        while(true) {
            cur = tree[cur].sufflink;
            curlen = tree[cur].len;

            if (pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) {
                tree[v].sufflink = tree[cur].next[let];
                break;
            }
        }
        // System.out.println(v + " " + pos);
        // tree[v].num = 1 + tree[tree[v].sufflink].num;

        return true;
    }

    private void init() {
        tree = new Node[MAX];
        tree[size] = new Node(-1);
        tree[size++].sufflink = 0;

        tree[size] = new Node(0);
        tree[size++].sufflink = 0;

        suff = size - 1;
    }

    class Node {
        int sufflink, len;
        int []next;
        // long num;

        public Node(int len) {
            next = new int[26];
            Arrays.fill(next, -1);

            sufflink = -1;
            this.len = len;
            // num = 0;
        }

        public String toString() {
            return "[len=" + len +", sufflink=" + sufflink + "]";
        }
    }

    public static void main(String args[]) throws Exception{
	   new Main().run();
    }
}