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».
//package com.a2onlinejudge.groupcontests.jan02_2017;

import java.io.*;
import java.util.*;

public final class QueriesForNumberOfPalindromes
{
    public static void main(String[] args)
    {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
		Solver solver = new Solver(in, out);

		try
		{
			solver.solve();
		}
		catch (IOException e)
		{
			e.printStackTrace();
		}

		in.close();
        out.flush();
        out.close();
    }

    static class Solver
    {
    	char[] s;
        int n, q;
        int[][] cnt;
        InputReader in;
        BufferedReader bf;
        PrintWriter out;

		void solve() throws IOException
		{
/*			s = in.next().toCharArray();
			n = s.length;
			q = in.nextInt();*/

			bf = new BufferedReader(new InputStreamReader(System.in));
			s = bf.readLine().toCharArray();
			n = s.length;
			q = Integer.parseInt(bf.readLine());

			pre();

			while (q-- > 0)
			{
				String[] tok = bf.readLine().split(" ");
				int left, right;

//				left = in.nextInt() - 1;
//				right = in.nextInt() - 1;
				left = Integer.parseInt(tok[0]) - 1;
				right = Integer.parseInt(tok[1]) - 1;
				out.println(cnt[left][right]);
			}
		}

		void pre()
		{
			cnt = new int[n][n];

			for (int i = 0; i < n; i++)
				markOdd(i);

			for (int i = 1; i < n; i++)
				markEven(i - 1, i);

			for (int i = 0; i < n; i++)
			{
				for (int j = 1; j < n; j++)
					cnt[i][j] += cnt[i][j - 1];
			}

/*			for (int i = 0; i < n; i++)
			{
				cnt[i][i] = 1;

				for (int j = i + 1; j < n; j++)
				{
					if (isPalindrome(i, j))
						cnt[i][j] = 1 + cnt[i][j - 1];
					else
						cnt[i][j] = cnt[i][j - 1];
				}
			}*/

/*			System.out.println("cnt :");
			System.out.println("0 1 2 3 4 5\n-----------");

			for (int i = 0; i < n; i++, System.out.println())
				for (int j = 0; j < n; j++)
					System.out.print(cnt[i][j] + " ");

			System.out.println();*/

			for (int i = n - 1; i >= 0; i--)
				pushUp(n - 2, i, cnt[n - 1][i]);

/*			System.out.println("cnt :");
			System.out.println("0 1 2 3 4 5\n-----------");

			for (int i = 0; i < n; i++, System.out.println())
				for (int j = 0; j < n; j++)
					System.out.print(cnt[i][j] + " ");

			System.out.println();*/
		}

		void markOdd(int center)
		{
			cnt[center][center] = 1;

			for (int left = center - 1, right = center + 1; left >= 0 && right < n; left--, right++)
			{
				if (s[left] != s[right])
					return;

				cnt[left][right] = 1;
			}
		}

		void markEven(int left, int right)
		{
			for (; left >= 0 && right < n; left--, right++)
			{
				if (s[left] != s[right])
					return;

				cnt[left][right] = 1;
			}
		}

		void pushUp(int row, int col, int add)
		{
			if (row == -1)
				return;

			cnt[row][col] += add;
			pushUp(row - 1, col, cnt[row][col]);
		}
/*
		boolean isPalindrome(int left, int right)
		{
			for (int i = left, j = right; i < j; i++, j--)
				if (s[i] != s[j])
					return false;

			return true;
		}*/

        public Solver(InputReader in, PrintWriter out)
        {
        	this.in = in;
        	this.out = out;
        }

	}

    static class InputReader
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        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 nextInt()
        {
            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 & 15;

                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public String next()
        {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            StringBuilder res = new StringBuilder();

            do
            {
                res.appendCodePoint(c);

                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public void close()
        {
            try
            {
                stream.close();
            } catch (IOException e)
            {
                e.printStackTrace();
            }
        }

    }

}

/*

caaaba
5
1 1
1 4
2 3
4 6
4 5

*/
