Problem: The length of the longest common prefix of two strings s=s_1 s_2 … s_n and t = t_1 t_2 … t_m is defined as the maximum k ≤ min(n, m) such that s_1 s_2 … s_k equals t_1 t_2 … t_k. Let's denote the longest common prefix of two strings s and t as lcp(s,t).

Z-function of a string s_1 s_2 ... s_n is a sequence of integers z_1, z_2, …, z_n, where z_i = lcp(s_1 s_2 … s_n,\ \ s_i s_{i+1} ... s_n). Ж-function of a string s is defined as z_1 + z_2 + … + z_n.

You're given a string s=s_1 s_2 … s_n and q queries. Each query is described by two integers l_i and r_i, where 1 ≤ l_i ≤ r_i ≤ n. The answer for the query is defined as Ж-function of the string s_{l_i} s_{l_i +1} … s_{r_i}.

Input

The first line contains the string s, consisting of lowercase English letters (1 ≤ |s| ≤ 200 000). The second line contains one integer q — the number of queries (1 ≤ q ≤ 200 000). Each of the following q lines contains two integers l_i and r_i, describing the query (1 ≤ l_i ≤ r_i ≤ |s|).

Output

For every query output one integer: the value of Ж-function of the corresponding substring.

Examples

Input


abbd
4
2 3
1 3
3 3
1 4


Output


3
3
1
4


Input


bbaaa
5
2 4
1 5
1 5
3 3
1 2


Output


3
6
6
1
3

Note

In the first sample case there are four queries:

  * the first query corresponds to the substring bb, and its Ж-function equals 2 + 1 = 3;
  * the second query corresponds to the substring abb, and its Ж-function equals 3 + 0 + 0 = 3;
  * the third query corresponds to the substring b, and its Ж-function equals 1.
  * the fourth query corresponds to the substring abdd, and its Ж-function equals 4 + 0 + 0 + 0= 4. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 400111;
struct BIT {
  long long a[maxn];
  int ti[maxn], curt;
  void clear() { curt++; }
  void add(int x, long long v) {
    for (int i = x; i < maxn; i += i & (-i)) {
      if (ti[i] != curt) ti[i] = curt, a[i] = 0;
      a[i] += v;
    }
  }
  long long query(int x) {
    long long ret = 0;
    for (int i = x; i; i -= i & (-i)) {
      if (ti[i] != curt) ti[i] = curt, a[i] = 0;
      ret += a[i];
    }
    return ret;
  }
} B0, B1;
struct data {
  vector<pair<int, pair<int, int> > > line;
  vector<pair<int, pair<int, long long *> > > qry;
  vector<pair<pair<int, int>, pair<int, long long *> > > qry2;
  void add_line(int l, int r, int h) {
    line.push_back(make_pair(h, make_pair(l, r)));
  }
  void add_query(int r, int a, int b, long long *it) {
    int h = b - r;
    qry.push_back(make_pair(h, make_pair(b, it)));
    qry2.push_back(make_pair(make_pair(h, -1), make_pair(r, it)));
    qry2.push_back(make_pair(make_pair(a, 1), make_pair(r, it)));
  }
  void solve() {
    sort(line.begin(), line.end());
    sort(qry.begin(), qry.end());
    sort(qry2.begin(), qry2.end());
    reverse(line.begin(), line.end());
    reverse(qry.begin(), qry.end());
    reverse(qry2.begin(), qry2.end());
    int it;
    it = 0;
    B0.clear();
    B1.clear();
    for (auto X : qry) {
      while (it < line.size() && line[it].first >= X.first) {
        int l = line[it].second.first + line[it].first;
        int r = line[it].second.second + line[it].first;
        B1.add(l, 1);
        B0.add(l, -(l - 1));
        B1.add(r + 1, -1);
        B0.add(r + 1, (l - 1) + r - l + 1);
        it++;
      }
      *X.second.second += B0.query(X.second.first) +
                          1ll * B1.query(X.second.first) * X.second.first;
    }
    it = 0;
    B0.clear();
    B1.clear();
    for (auto X : qry2) {
      while (it < line.size() && line[it].first >= X.first.first) {
        int l = line[it].second.first;
        int r = line[it].second.second;
        B1.add(l, 1);
        B0.add(l, -(l - 1));
        B1.add(r + 1, -1);
        B0.add(r + 1, (l - 1) + r - l + 1);
        it++;
      }
      *X.second.second +=
          X.first.second * (B0.query(X.second.first) +
                            1ll * B1.query(X.second.first) * X.second.first);
    }
  }
} D[maxn];
int go[maxn][26], pre[maxn], len[maxn], tot = 1;
vector<int> son[maxn];
int hson[maxn], top[maxn], sz[maxn];
int append(int p, int c) {
  int np = ++tot;
  len[np] = len[p] + 1;
  while (p && !go[p][c]) go[p][c] = np, p = pre[p];
  if (!p) {
    pre[np] = 1;
    return np;
  }
  int q = go[p][c];
  if (len[q] == len[p] + 1)
    pre[np] = q;
  else {
    int nq = ++tot;
    len[nq] = len[p] + 1;
    for (int i = 0; i < 26; i++) go[nq][i] = go[q][i];
    pre[nq] = pre[q];
    pre[q] = pre[np] = nq;
    while (p && go[p][c] == q) go[p][c] = nq, p = pre[p];
  }
  return np;
}
int n;
char s[maxn];
int st[maxn];
void dfs(int x) {
  sz[x] = 1;
  for (auto u : son[x]) {
    dfs(u);
    sz[x] += sz[u];
    if (sz[u] > sz[hson[x]]) hson[x] = u;
  }
}
void dfs2(int x, int tp) {
  top[x] = tp;
  if (hson[x]) dfs2(hson[x], tp);
  for (auto u : son[x]) {
    if (u != hson[x]) dfs2(u, u);
  }
}
void add_suffix(int id) {
  int x = st[id];
  while (x) {
    D[top[x]].add_line(len[pre[top[x]]] + 1, len[x], id);
    x = pre[top[x]];
  }
}
void prework() {
  st[n + 1] = 1;
  for (int i = n; i >= 1; i--) {
    st[i] = append(st[i + 1], s[i] - 'a');
  }
  for (int i = 2; i <= tot; i++) son[pre[i]].push_back(i);
  dfs(1);
  dfs2(1, 1);
  for (int i = 1; i <= n; i++) {
    add_suffix(i);
  }
}
int q;
long long ans[maxn];
void add_query(int l, int r, long long *it) {
  int x = st[l];
  while (x) {
    int L = len[pre[top[x]]] + 1;
    if (L <= r - l + 1) {
      D[top[x]].add_query(min(r - l + 1, len[x]), l, r + 1, it);
    }
    x = pre[top[x]];
  }
}
void solve() {
  for (int i = 1; i <= tot; i++) D[i].solve();
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  prework();
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    add_query(l, r, &ans[i]);
  }
  solve();
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}