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 double pi = 2 * acos(0.0);
template <typename T>
T Sqr(T x) {
  T n = x * x;
  return n;
}
template <typename T>
T Pow(T B, T P) {
  if (P == 0) return 1;
  if (P & 1)
    return B * Pow(B, P - 1);
  else
    return Sqr(Pow(B, P / 2));
}
template <typename T>
T Abs(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
template <typename T>
void Print(T ar[], int a, int b) {
  for (int i = a; i + 1 <= b; i++) cout << ar[i] << " ";
  cout << ar[b] << "\n";
}
template <typename T>
void Print(T ar[], int n) {
  for (int i = 0; i + 1 < n; i++) cout << ar[i] << " ";
  cout << ar[n - 1] << "\n";
}
template <typename T>
void Print(const vector<T> &v) {
  for (int i = 0; i + 1 < v.size(); i++) cout << v[i] << " ";
  cout << v.back() << "\n";
}
struct ModularExponentiation {
  template <typename T>
  T Pow(T b, T p) {
    T res = 1;
    while (p > 0) {
      if (p % 2 == 1) res = res * b;
      b = b * b;
      p /= 2;
    }
    return res;
  }
  template <typename T>
  T Mod(T a, T m) {
    return (((a % m) + m) % m);
  }
  template <typename T>
  T BigMod(T b, T p, T m) {
    T res = 1;
    if (b > m) b %= m;
    while (p) {
      if (p % 2 == 1) res = res * b % m;
      b = b * b % m;
      p /= 2;
    }
    return res;
  }
  template <typename T>
  T ModInv(T b, T m) {
    return BigMod(b, m - 2, m);
  }
};
struct Hashing {
  long long base[2] = {1949313259, 1997293877};
  long long mod[2] = {2091573227, 2117566807};
  vector<long long> pow[2], inv[2];
  vector<long long> prehash[2], sufhash[2];
  int maxN, flag = 0, len;
  void Init(int n) {
    maxN = n + 2;
    for (int i = 0; i < 2; i++) {
      pow[i].resize(maxN);
      inv[i].resize(maxN);
    }
    Generate();
  }
  void Generate() {
    ModularExponentiation Ex;
    for (int j = 0; j < 2; j++) {
      pow[j][0] = 1;
      inv[j][0] = 1;
      long long minv = Ex.ModInv(base[j], mod[j]);
      for (int i = 1; i < maxN; i++) {
        pow[j][i] = pow[j][i - 1] * base[j] % mod[j];
        inv[j][i] = inv[j][i - 1] * minv % mod[j];
      }
    }
  }
  long long GetHash(string &s) {
    long long hash_val[2] = {0, 0};
    int n = s.size();
    for (int j = 0; j < 2; j++) {
      for (int i = 0; i < n; i++) {
        hash_val[j] = (hash_val[j] + s[i] * pow[j][i]) % mod[j];
      }
    }
    return (hash_val[0] << 32LL) | hash_val[1];
  }
  void ComputeHash(string &s) {
    flag = 1;
    len = s.size();
    for (int j = 0; j < 2; j++) prehash[j].resize(maxN);
    for (int j = 0; j < 2; j++) prehash[j][0] = 0;
    for (int j = 0; j < 2; j++) {
      for (int i = 0; i < len; i++) {
        prehash[j][i + 1] = (prehash[j][i] + pow[j][i] * s[i]) % mod[j];
      }
    }
  }
  long long GetSubstrHash(int l, int r) {
    if (!flag) {
      cout << "ComputeHash\n";
      return -1;
    }
    long long hash_val[2];
    for (int j = 0; j < 2; j++)
      hash_val[j] = (prehash[j][r + 1] - prehash[j][l]) * inv[j][l] % mod[j];
    for (int j = 0; j < 2; j++)
      if (hash_val[j] < 0) hash_val[j] += mod[j];
    return (hash_val[0] << 32) | hash_val[1];
  }
  void ComputePreAndSufHash(string &s) {
    flag = 1;
    len = s.size();
    for (int j = 0; j < 2; j++) {
      prehash[j].resize(maxN);
      sufhash[j].resize(maxN);
    }
    for (int j = 0; j < 2; j++) prehash[j][0] = sufhash[j][0] = 0;
    for (int j = 0; j < 2; j++) {
      for (int i = 0; i < len; i++) {
        prehash[j][i + 1] = (prehash[j][i] + pow[j][i] * s[i]) % mod[j];
        sufhash[j][i + 1] =
            (sufhash[j][i] + pow[j][len - i + 1] * s[i]) % mod[j];
      }
    }
  }
  long long GetPrefixHash(int l, int r) { return GetSubstrHash(l, r); }
  long long GetSuffixHash(int l, int r) {
    if (!flag) {
      cout << "ComputePreAndSufHash\n";
      return -1;
    }
    long long hash_val[2];
    for (int j = 0; j < 2; j++)
      hash_val[j] =
          (sufhash[j][r + 1] - sufhash[j][l]) * inv[j][len - r + 1] % mod[j];
    for (int j = 0; j < 2; j++)
      if (hash_val[j] < 0) hash_val[j] += mod[j];
    return (hash_val[0] << 32) | hash_val[1];
  }
  bool IsPallindrome(int l, int r) {
    return (GetPrefixHash(l, r) == GetSuffixHash(l, r));
  }
  vector<int> RabinKarp(string &txt, string &ptrn) {
    ComputeHash(txt);
    long long ptrn_hash = GetHash(ptrn);
    vector<int> occurences;
    int txtlen = txt.size();
    int ptrnlen = ptrn.size();
    for (int i = 0; i < txtlen - ptrnlen + 1; i++) {
      long long cur_hash = GetSubstrHash(i, ((i + ptrnlen) - 1));
      if (cur_hash == ptrn_hash) occurences.emplace_back(i + 1);
    }
    return occurences;
  }
};
int mark[5002][5002];
int ans[5002][5002];
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  Hashing h;
  h.Init(5002);
  h.ComputePreAndSufHash(s);
  int len = s.size();
  for (int i = 0; i < len; i++) {
    for (int j = i, cnt = 0; j < len; j++) {
      if (h.IsPallindrome(i, j)) {
        mark[i][j] = 1;
      }
    }
  }
  int sum;
  for (int i = 0; i < len; i++) {
    sum = 0;
    for (int j = 0; j < len; j++) {
      sum += mark[i][j];
      ans[i + 1][j + 1] = ans[i][j + 1] + sum;
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << (ans[r][r] - ans[l - 1][r] - ans[r][l - 1] + ans[l - 1][l - 1])
         << "\n";
  }
  return 0;
}
