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 N = 6e5 + 10;
vector<int> g[N];
int w[N], pos[N];
struct SAM {
  int len[N], fa[N], ch[N][26], sz, last;
  SAM() { sz = last = 1; }
  void extend(int c, int id) {
    int cur = ++sz, p = last;
    last = cur;
    pos[id] = cur;
    len[cur] = len[p] + 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = cur;
    if (!p)
      fa[cur] = 1;
    else {
      int q = ch[p][c];
      if (len[q] == len[p] + 1)
        fa[cur] = q;
      else {
        int clone = ++sz;
        memcpy(ch[clone], ch[q], sizeof(ch[q]));
        len[clone] = len[p] + 1;
        fa[clone] = fa[q];
        fa[q] = fa[cur] = clone;
        for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = clone;
      }
    }
  }
  void build_g() {
    for (int i = 2; i <= sz; ++i)
      g[fa[i]].push_back(i), w[i] = len[i] - len[fa[i]], 42;
  }
} sam;
int n;
int siz[N], top[N], son[N], dep[N], fa[N], dfn[N], rnk[N], cnt;
struct node {
  long long sum, tag, wight;
};
struct ST {
  node t[N * 4];
  void pdown(int o, int l, int r) {
    if (!t[o].tag) return;
    t[(o << 1)].tag += t[o].tag;
    t[(o << 1 | 1)].tag += t[o].tag;
    t[(o << 1)].sum += t[o].tag * t[(o << 1)].wight;
    t[(o << 1 | 1)].sum += t[o].tag * t[(o << 1 | 1)].wight;
    t[o].tag = 0;
  }
  void pup(int o) { t[o].sum = t[(o << 1)].sum + t[(o << 1 | 1)].sum; }
  void build(int o, int l, int r) {
    t[o].tag = 0;
    if (l == r) {
      t[o].wight = w[rnk[l]];
      t[o].sum = 0;
      return;
    }
    build((o << 1), l, ((l + r) >> 1));
    build((o << 1 | 1), ((l + r) >> 1) + 1, r);
    pup(o);
    t[o].wight = t[(o << 1)].wight + t[(o << 1 | 1)].wight;
  }
  void upd(int o, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
      t[o].tag += v;
      t[o].sum += v * t[o].wight;
      return;
    }
    pdown(o, l, r);
    if (ql <= ((l + r) >> 1)) upd((o << 1), l, ((l + r) >> 1), ql, qr, v);
    if (qr > ((l + r) >> 1))
      upd((o << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, v);
    pup(o);
  }
  long long qrysum(int o, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return t[o].sum;
    pdown(o, l, r);
    return qrysum((o << 1), l, ((l + r) >> 1), ql, qr) +
           qrysum((o << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr);
  }
} st;
const int M = 19 + 1;
int BZ[N][M];
void dfs1(int u, int f) {
  son[u] = 0;
  siz[u] = 1;
  BZ[u][0] = f;
  for (int i = 1; i <= M - 1; ++i) BZ[u][i] = BZ[BZ[u][i - 1]][i - 1];
  for (int v : g[u])
    if (!dep[v]) {
      dep[v] = dep[u] + 1;
      fa[v] = u;
      dfs1(v, u);
      siz[u] += siz[v];
      if (!son[u] || siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
  top[u] = t;
  dfn[u] = ++cnt;
  rnk[cnt] = u;
  if (!son[u]) return;
  dfs2(son[u], t);
  for (int v : g[u])
    if (v != son[u] && v != fa[u]) dfs2(v, v);
}
long long qrysum(int x, int y) {
  long long res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res += st.qrysum(1, 1, n, dfn[top[x]], dfn[x]), x = fa[top[x]];
  }
  if (dfn[x] > dfn[y]) swap(x, y);
  res += st.qrysum(1, 1, n, dfn[x], dfn[y]);
  return res;
}
void upd_chain(int x, int y, int v) {
  int fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      st.upd(1, 1, n, dfn[fx], dfn[x], v), x = fa[fx];
    else
      st.upd(1, 1, n, dfn[fy], dfn[y], v), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (x != y) {
    if (dfn[x] < dfn[y])
      st.upd(1, 1, n, dfn[x], dfn[y], v);
    else
      st.upd(1, 1, n, dfn[y], dfn[x], v);
  } else
    st.upd(1, 1, n, dfn[x], dfn[y], v);
}
struct Qry {
  int l, r, id;
  bool operator<(const Qry& A) const { return l < A.l; }
} Q[N];
struct Rec {
  int x, y, id;
  bool operator<(const Rec& A) const { return y - x < A.y - A.x; }
};
struct Line {
  int d, l, r;
  bool operator<(const Line& A) const { return d < A.d; }
};
struct node2 {
  long long sum, tag;
};
struct ST2 {
  node2 t[N * 4];
  void pdown(int o, int l, int r) {
    if (!t[o].tag) return;
    t[(o << 1)].tag += t[o].tag;
    t[(o << 1 | 1)].tag += t[o].tag;
    t[(o << 1)].sum += t[o].tag * (((l + r) >> 1) - l + 1);
    t[(o << 1 | 1)].sum += t[o].tag * (r - ((l + r) >> 1));
    t[o].tag = 0;
  }
  void pup(int o) { t[o].sum = t[(o << 1)].sum + t[(o << 1 | 1)].sum; }
  void build(int o, int l, int r) {
    t[o].tag = 0;
    if (l == r) {
      t[o].sum = w[rnk[l]];
      return;
    }
    build((o << 1), l, ((l + r) >> 1));
    build((o << 1 | 1), ((l + r) >> 1) + 1, r);
    pup(o);
  }
  void upd(int o, int l, int r, int ql, int qr, int v) {
    if (ql > qr) return;
    if (ql <= l && r <= qr) {
      t[o].tag += v;
      t[o].sum += v * (r - l + 1);
      return;
    }
    pdown(o, l, r);
    if (ql <= ((l + r) >> 1)) upd((o << 1), l, ((l + r) >> 1), ql, qr, v);
    if (qr > ((l + r) >> 1))
      upd((o << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, v);
    pup(o);
  }
  long long qrysum(int o, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return t[o].sum;
    pdown(o, l, r);
    return qrysum((o << 1), l, ((l + r) >> 1), ql, qr) +
           qrysum((o << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr);
  }
} st2;
vector<Line> line[N];
vector<Rec> rec[N];
long long ans[N];
char s[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s + 1;
  int s_sz = strlen(s + 1);
  for (int i = s_sz; i >= 1; --i) sam.extend(s[i] - 'a', i);
  sam.build_g();
  for (int i = 1; i <= s_sz; ++i) 42;
  n = sam.sz;
  dep[1] = 1;
  dfs1(1, 0), dfs2(1, 1);
  st.build(1, 1, n);
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> Q[i].l >> Q[i].r, Q[i].id = i;
  }
  sort(Q + 1, Q + 1 + q, [&](const Qry& l, const Qry& r) { return l.l < r.l; });
  int now = 0;
  for (int i = 1; i <= q; ++i) {
    while (now < Q[i].l - 1) ++now, upd_chain(1, pos[now], 1);
    int u = pos[Q[i].l];
    for (int j = M - 1; j >= 0; --j)
      if (sam.len[BZ[u][j]] >= Q[i].r - Q[i].l + 1) u = BZ[u][j];
    if (w[dfn[u]])
      ans[Q[i].id] -= st.qrysum(1, 1, n, dfn[u], dfn[u]) / w[u] *
                      (min(Q[i].r - Q[i].l + 1, sam.len[u]) - sam.len[fa[u]]);
    ans[Q[i].id] -= qrysum(1, fa[u]);
  }
  for (int i = 1; i <= q; ++i) 42;
  for (int i = 1; i <= s_sz; ++i) {
    int u = pos[i];
    while (u) {
      int Top = top[u];
      line[Top].push_back({i, sam.len[fa[Top]] + 1, sam.len[u]});
      u = fa[Top];
    }
  }
  for (int i = 1; i <= q; ++i) {
    int l = Q[i].l, r = Q[i].r, id = Q[i].id;
    int u = pos[l];
    while (u) {
      int Top = top[u];
      rec[Top].push_back({min(r - l + 1, sam.len[u]), r + 1, id});
      u = fa[Top];
    }
  }
  for (int i = 1; i <= n; ++i) {
    sort((line[i]).begin(), (line[i]).end());
    sort((rec[i]).begin(), (rec[i]).end());
    int szL = line[i].size(), szR = rec[i].size();
    int L = 0, R = 0;
    while (L <= szL && R < szR) {
      if (L < szL && line[i][L].d <= rec[i][R].y - rec[i][R].x) {
        st2.upd(1, 1, n, line[i][L].l, line[i][L].r, 1);
        L++;
      } else {
        ans[rec[i][R].id] += st2.qrysum(1, 1, n, 1, rec[i][R].x);
        R++;
      }
    }
    for (int j = 0; j < L; j++)
      st2.upd(1, 1, n, line[i][j].l, line[i][j].r, -1);
    for (auto& I : rec[i]) swap(I.x, I.y);
    for (auto& I : line[i]) {
      I.l += I.d, I.r += I.d;
      I.d = -I.d;
    }
    sort((line[i]).begin(), (line[i]).end());
    sort((rec[i]).begin(), (rec[i]).end());
    L = 0, R = 0;
    while (L <= szL && R < szR) {
      if (L < szL && line[i][L].d < rec[i][R].y - rec[i][R].x) {
        st2.upd(1, 1, n, line[i][L].l, line[i][L].r, 1);
        L++;
      } else {
        ans[rec[i][R].id] += st2.qrysum(1, 1, n, 1, rec[i][R].x);
        R++;
      }
    }
    for (int j = 0; j < L; j++)
      st2.upd(1, 1, n, line[i][j].l, line[i][j].r, -1);
  }
  for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}