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;
char s[200010];
int L[200010], R[200010];
int n, q;
vector<int> from[400010];
int pos[200010];
int fa[400010], len[400010];
int dep[400010], son[400010], id[400010], sz[400010], TOT, tp[400010],
    seq[400010];
long long ans[200010];
vector<pair<int, int> > qry[400010], mdy[400010];
struct SAM {
  int son[400010][26], TOT, lst;
  void clear() {
    memset(son, 0, sizeof(son)), len[1] = 0, fa[1] = 0, TOT = lst = 1;
  }
  int append(int x) {
    int p = lst, np = ++TOT;
    len[np] = len[p] + 1;
    while (p && !son[p][x]) son[p][x] = np, p = fa[p];
    if (p) {
      int q = son[p][x];
      if (len[q] == len[p] + 1)
        fa[np] = q;
      else {
        int nq = ++TOT;
        memcpy(son[nq], son[q], sizeof(son[q])), len[nq] = len[p] + 1;
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        while (p && son[p][x] == q) son[p][x] = nq, p = fa[p];
      }
    } else
      fa[np] = 1;
    return lst = np;
  }
  void BuildT() {
    for (int i = 2; i <= TOT; i++) from[fa[i]].push_back(i);
  }
} sam;
void dfs1(int x, int last) {
  sz[x] = 1, son[x] = -1;
  for (auto v : from[x])
    if (v != last) {
      dep[v] = dep[x] + 1, dfs1(v, x), sz[x] += sz[v];
      if (son[x] == -1 || sz[v] > sz[son[x]]) son[x] = v;
    }
}
void dfs2(int x, int t) {
  id[x] = ++TOT, seq[TOT] = x, tp[x] = t;
  if (son[x] == -1) return;
  dfs2(son[x], t);
  for (auto v : from[x])
    if (v != fa[x] && v != son[x]) dfs2(v, v);
}
void AddQry(int id) {
  int x = pos[L[id]], l = R[id] - L[id] + 1;
  while (tp[x] != 1) {
    if (len[fa[tp[x]]] < l)
      qry[tp[x]].push_back(make_pair(min(l, len[x]) - len[fa[tp[x]]], id));
    x = fa[tp[x]];
  }
  qry[tp[x]].push_back(make_pair(min(l, len[x]), id));
}
void AddMdy(int id) {
  int x = pos[id];
  while (tp[x] != 1)
    mdy[tp[x]].push_back(make_pair(len[x] - len[fa[tp[x]]], id)), x = fa[tp[x]];
  mdy[tp[x]].push_back(make_pair(len[x] - len[fa[tp[x]]], id));
}
bool cmpm(pair<int, int> x, pair<int, int> y) {
  return x.first + x.second < y.first + y.second;
}
bool cmpq1(pair<int, int> x, pair<int, int> y) {
  return R[x.second] < R[y.second];
}
bool cmpq2(pair<int, int> x, pair<int, int> y) {
  return R[x.second] - x.first < R[y.second] - y.first;
}
struct BIT {
  long long T[200010][2];
  int vis[200010], VIS;
  BIT() { memset(vis, 0, sizeof(vis)), VIS = 2333; }
  void clear() { VIS++; }
  void Flush(int x) {
    if (vis[x] != VIS) vis[x] = VIS, T[x][0] = T[x][1] = 0;
  }
  void insert(int x, int v) {
    while (x <= 200005) Flush(x), T[x][0]++, T[x][1] += v, x += x & -x;
  }
  void erase(int x, int v) {
    while (x <= 200005) Flush(x), T[x][0]--, T[x][1] -= v, x += x & -x;
  }
  long long query0(int x) {
    long long res = 0;
    while (x) Flush(x), res += T[x][0], x -= x & -x;
    return res;
  }
  long long query1(int x) {
    long long res = 0;
    while (x) Flush(x), res += T[x][1], x -= x & -x;
    return res;
  }
} up, dw;
void Solve(int x) {
  sort(mdy[x].rbegin(), mdy[x].rend()), sort(qry[x].rbegin(), qry[x].rend());
  int pos = 0;
  up.clear(), dw.clear();
  for (auto it : mdy[x]) up.insert(it.second, it.first);
  for (auto it : qry[x]) {
    int lim = R[it.second] + 1 - len[fa[x]];
    while (pos < mdy[x].size() && mdy[x][pos].first >= it.first) {
      up.erase(mdy[x][pos].second, mdy[x][pos].first);
      dw.insert(mdy[x][pos].second, mdy[x][pos].first);
      pos++;
    }
    int tmp = lim - it.first;
    ans[it.second] -= up.query1(L[it.second] - 1);
    ans[it.second] -= dw.query0(L[it.second] - 1) * it.first;
    int old = ans[it.second];
    ans[it.second] -= it.first * up.query0(tmp) - up.query1(tmp);
  }
  sort(mdy[x].begin(), mdy[x].end(), cmpm);
  sort(qry[x].begin(), qry[x].end(), cmpq1);
  up.clear(), dw.clear(), pos = 0;
  for (auto it : mdy[x]) up.insert(it.second, it.second);
  for (auto it : qry[x]) {
    int lim = R[it.second] + 1 - len[fa[x]];
    while (pos < mdy[x].size() &&
           mdy[x][pos].first + mdy[x][pos].second <= lim) {
      up.erase(mdy[x][pos].second, mdy[x][pos].second);
      dw.insert(mdy[x][pos].second, mdy[x][pos].first);
      pos++;
    }
    ans[it.second] += lim * up.query0(lim) - up.query1(lim);
    ans[it.second] += dw.query1(lim);
    int tmp = lim - it.first;
    ans[it.second] -= tmp * up.query0(tmp) - up.query1(tmp);
    ans[it.second] -= dw.query1(tmp) - dw.query0(tmp) * it.first;
  }
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  sam.clear();
  for (int i = n; i >= 1; i--) pos[i] = sam.append(s[i] - 'a');
  sam.BuildT(), dfs1(1, 1), dfs2(1, 1);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) scanf("%d%d", &L[i], &R[i]), AddQry(i);
  for (int i = 1; i <= n; i++) AddMdy(i);
  for (int i = 1; i <= TOT; i++)
    if (tp[i] == i) Solve(i);
  for (int i = 0; i < q; i++) printf("%lld\n", ans[i]);
  return 0;
}