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.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

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

class QueriesForNumberOfPalindrome {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        String type =  in.readString();
        int charCount   =   type.length();
        boolean[][] isPalindrome    =   new boolean[charCount+1][charCount+1] ;
        int[][] dp  =   new int[charCount+1][charCount+1];
        ArrayUtils.fill(isPalindrome, false);
        ArrayUtils.fill(dp,0);
        // all one length strings are palindrome
        for(int i   =   0;i < charCount ; i++) {
            isPalindrome[i][i] =    true;
            dp[i][i]    =   1;
        }

        for(int len =   2;len <= charCount;len++) {

            for(int j   =   0;(len + j -1) < charCount;j++) {
                int start   =   j;
                int end     =   len+j-1;
                if(len  ==  2) {
                    isPalindrome[start][end] =   (type.charAt(start)==    type.charAt(end));

                } else {
                    isPalindrome[start][end] =   isPalindrome[start+1][end-1] &&
                            (type.charAt(start)==    type.charAt(end));
                }

                dp[start][end]  =   dp[start][end-1]+dp[start+1][end]-dp[start+1][end-1];
                if(isPalindrome[start][end]){
                    dp[start][end]+=1;
                }
            }

        }

        int queryCount  =   in.readInt();
        for(int i   =   queryCount;i != 0 ; i--) {
            out.printLine(dp[in.readInt()-1][in.readInt()-1]);
        }

    }
}

class InputReader {

    private InputStream stream;

    private byte[] buf = new byte[1024];

    private int curChar;

    private int numChars;

    private SpaceCharFilter filter;
    public InputReader(InputStream stream) {

        this.stream = stream;

    }



    public int read() {

        if (numChars == -1)

            throw new InputMismatchException();

        if (curChar >= numChars) {

            curChar = 0;

            try {

                numChars = stream.read(buf);

            } catch (IOException e) {

                throw new InputMismatchException();

            }

            if (numChars <= 0)

                return -1;

        }

        return buf[curChar++];

    }



    public int readInt() {

        int c = read();

        while (isSpaceChar(c))

            c = read();

        int sgn = 1;

        if (c == '-') {

            sgn = -1;

            c = read();

        }

        int res = 0;

        do {

            if (c < '0' || c > '9')

                throw new InputMismatchException();

            res *= 10;

            res += c - '0';

            c = read();

        } while (!isSpaceChar(c));

        return res * sgn;

    }



    public String readString() {

        int c = read();

        while (isSpaceChar(c))

            c = read();

        StringBuffer res = new StringBuffer();

        do {

            res.appendCodePoint(c);

            c = read();

        } while (!isSpaceChar(c));

        return res.toString();

    }



    public boolean isSpaceChar(int c) {

        if (filter != null)

            return filter.isSpaceChar(c);

        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;

    }



    public interface SpaceCharFilter {

        public boolean isSpaceChar(int ch);

    }

}

class OutputWriter {

    private final PrintWriter writer;
    public OutputWriter(OutputStream outputStream) {

        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));

    }



    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }



    public void print(Object...objects) {

        for (int i = 0; i < objects.length; i++) {

            if (i != 0)

                writer.print(' ');

            writer.print(objects[i]);

        }

    }



    public void printLine(Object...objects) {

        print(objects);

        writer.println();

    }



    public void close() {

        writer.close();

    }



    }

class ArrayUtils {


    public static void fill(int[][] array,int value) {
        for(int[] i : array) {
            Arrays.fill(i,value);
        }
    }
    public static void fill(boolean[][] array,boolean value) {
        for(boolean[] i: array){
            Arrays.fill(i,value);
        }
    }


    }

