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;
template <class T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
T my_pow(T n, T p) {
  if (p == 0) return 1;
  T x = my_pow(n, p / 2);
  x = (x * x);
  if (p & 1) x = (x * n);
  return x;
}
template <class T>
T big_mod(T n, T p, T m) {
  if (p == 0) return (T)1;
  T x = big_mod(n, p / 2, m);
  x = (x * x) % m;
  if (p & 1) x = (x * n) % m;
  return x;
}
template <class T>
T extract(string s, T ret) {
  stringstream ss(s);
  ss >> ret;
  return ret;
}
string itos(int n) {
  string s;
  while (n) {
    s += (n % 10 + 48);
    n /= 10;
  }
  reverse(s.begin(), s.end());
  return s;
}
int stoi(string s) {
  int n = 0;
  for (__typeof(s.size()) i = 0; i < (s.size()); i++) n = n * 10 + (s[i] - 48);
  return n;
}
double DEG(double x) { return (180.0 * x) / (acos(-1.0)); }
double RAD(double x) { return (x * (double)acos(-1.0)) / (180.0); }
template <typename T>
T DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
int isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
const int N = 1e5 + 5, MOD = 1e9 + 7;
int ar[N], br[N];
int a = 0, b = 0, c = 0, r = 0, rr = 0, res = 0, n, m, t = 0, ks = 0;
string s;
int dp[5001][5001];
int dp1[5001][5001];
int pal(int i, int j) {
  if (i >= j) return 1;
  int &ret1 = dp1[i][j];
  if (ret1 != -1) return ret1;
  ret1 = 0;
  if (s[i] == s[j])
    ret1 |= pal(i + 1, j - 1);
  else
    return ret1 = 0;
  return ret1;
}
int go(int i, int j) {
  if (i == j) return 1;
  if (i > j) return 0;
  int &ret = dp[i][j];
  if (ret != -1) return ret;
  ret = 0;
  if (pal(i, j)) ret = 1;
  ret += go(i + 1, j);
  ret += go(i, j - 1);
  ret -= go(i + 1, j - 1);
  return ret;
}
int main() {
  memset(dp, -1, sizeof(dp));
  memset(dp1, -1, sizeof(dp1));
  cin >> s;
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &a, &b);
    a--, b--;
    printf("%d\n", go(a, b));
  }
  return 0;
}
