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».
#include <bits/stdc++.h>
using namespace std;
const long long int INF = (long long int)(8e18);
const long long int MOD = 1000000007;
long long int prefix[5010], suffix[5010], power[5010], dp[5010][5010],
    FindMMI[5010];
long long int modPow(long long int base, long long int exponent) {
  if (exponent == 0) return 1;
  if (exponent == 1) return base;
  long long int temp = modPow(base, exponent >> 1);
  long long int val = temp % MOD;
  if (exponent % 2 == 0)
    return (val * val) % MOD;
  else
    return (((val * val) % MOD) * (base % MOD)) % MOD;
}
long long int findMMI(long long int n) { return modPow(n, MOD - 2); }
void computePrefixHash(string str, int n) {
  prefix[0] = 0;
  prefix[1] = str[0];
  for (long long int i = 2; i <= n; i++)
    prefix[i] =
        (prefix[i - 1] % MOD + (str[i - 1] % MOD * power[i - 1] % MOD) % MOD) %
        MOD;
  return;
}
void computeSuffixHash(string str, int n) {
  suffix[0] = 0;
  suffix[1] = str[n - 1];
  for (long long int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
    suffix[j] =
        (suffix[j - 1] % MOD + (str[i] % MOD * power[j - 1] % MOD) % MOD) % MOD;
  return;
}
void queryResults(string s) {
  long long int n = s.length();
  for (long long int i = 0; i < n; i++) {
    for (long long int j = i; j < n; j++) {
      long long int hash_LR =
          ((prefix[j + 1] - prefix[i] + MOD) % MOD * FindMMI[i] % MOD) % MOD;
      long long int reverse_hash_LR =
          ((suffix[n - i] - suffix[n - j - 1] + MOD) % MOD *
           FindMMI[n - j - 1] % MOD) %
          MOD;
      if (hash_LR == reverse_hash_LR) {
        dp[i + 1][j + 1]++;
      }
    }
  }
  return;
}
void computePowers(int n) {
  power[0] = 1;
  for (long long int i = 1; i <= n; i++)
    power[i] = (power[i - 1] % MOD * 101 % MOD) % MOD;
  return;
}
int main() {
  ios ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  int q;
  cin >> q;
  computePowers(s.length());
  computePrefixHash(s, s.length());
  computeSuffixHash(s, s.length());
  for (int i = 0; i <= 5010 - 1; i++) {
    FindMMI[i] = findMMI(power[i]) % MOD;
  }
  queryResults(s);
  for (long long int i = 1; i <= s.length(); i++) {
    for (long long int j = 1; j <= s.length(); j++) {
      dp[i][j] += dp[i][j - 1];
    }
  }
  for (long long int i = 1; i <= s.length(); i++) {
    for (long long int j = i; j >= 1; j--) {
      if (i > j) dp[i][j] += (dp[i][j + 1] + dp[j][i]);
    }
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << dp[r][l] << '\n';
  }
  return 0;
}
