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.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.io.*;
import java.math.*;
import java.text.*; 
import java.util.*;

/*
br = new BufferedReader(new FileReader("input.txt"));
pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 */

public class Main {
  private static BufferedReader br;
  private static StringTokenizer st;
  private static PrintWriter pw;

  public static void main(String[] args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    //int qq = 1;
    int qq = Integer.MAX_VALUE;
    //int qq = readInt();
    for(int casenum = 1; casenum <= qq; casenum++)  {
      String s = nextToken();
      int n = s.length();
      boolean[][] pal = new boolean[s.length()][s.length()];
      for(int i = 0; i < s.length(); i++) {
        pal[i][i] = true;
        if(i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {
          pal[i][i+1] = true;
        }
      }
      for(int diff = 2; diff < n; diff++) {
        for(int i = 0; i + diff < n; i++) {
          pal[i][i+diff] = pal[i+1][i+diff-1] && s.charAt(i) == s.charAt(i+diff);
        }
      }
      int[][] dp = new int[n][n];
      for(int i = 0; i < n; i++) {
        dp[i][i] = 1;
        if(i+1 < n && pal[i][i+1]) {
          dp[i][i+1] = 3;
        }
        else if(i+1 < n) {
          dp[i][i+1] = 2;
        }
      }
      for(int diff = 2; diff < n; diff++) {
        for(int i = 0; i + diff < n; i++) {
          dp[i][i+diff] = dp[i+1][i+diff] + dp[i][i+diff-1] - dp[i+1][i+diff-1];
          if(pal[i][i+diff]) {
            dp[i][i+diff]++;
          }
        }
      }
      int qqq = readInt();
      while(qqq-- > 0) {
        int a = readInt();
        int b = readInt();
        pw.println(dp[--a][--b]);
      }
    }
    pw.close();
  }

  private static void exitImmediately() {
    pw.close();
    System.exit(0);
  }

  private static long readLong() throws IOException {
    return Long.parseLong(nextToken());
  }

  private static double readDouble() throws IOException {
    return Double.parseDouble(nextToken());
  }

  private static int readInt() throws IOException {
    return Integer.parseInt(nextToken());
  }

  private static String nextToken() throws IOException  {
    while(st == null || !st.hasMoreTokens())  {
      if(!br.ready()) {
        exitImmediately();
      }
      st = new StringTokenizer(br.readLine().trim());
    }
    return st.nextToken();
  }
}


