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 long long maxn = 4e5 + 58;
using ll = long long;
struct smt {
  long long n, size, rt;
  long long ls[maxn << 1], rs[maxn << 1];
  ll tag[maxn << 1];
  ll cnt[maxn << 1], sum[maxn << 1];
  void init(long long sz, long long *tmp) {
    size = rt = 0, n = sz, bld(rt, 1, n, tmp);
  }
  void up(long long p) { sum[p] = sum[ls[p]] + sum[rs[p]]; }
  void bld(long long &p, long long l, long long r, long long *tmp) {
    p = ++size;
    if (l == r) {
      cnt[p] = tmp[l];
      return;
    }
    long long mid = l + r >> 1;
    bld(ls[p], l, mid, tmp);
    bld(rs[p], mid + 1, r, tmp);
    cnt[p] = cnt[ls[p]] + cnt[rs[p]];
  }
  void down(long long p) {
    if (tag[p]) {
      tag[ls[p]] += tag[p], sum[ls[p]] += tag[p] * cnt[ls[p]];
      tag[rs[p]] += tag[p], sum[rs[p]] += tag[p] * cnt[rs[p]];
      tag[p] = 0;
    }
  }
  void mdf(long long p, long long ql, long long qr, long long l, long long r,
           long long v) {
    if (ql <= l && r <= qr) {
      tag[p] += v, sum[p] += v * cnt[p];
      return;
    }
    down(p);
    long long mid = l + r >> 1;
    if (ql <= mid) mdf(ls[p], ql, qr, l, mid, v);
    if (qr > mid) mdf(rs[p], ql, qr, mid + 1, r, v);
    up(p);
  }
  void mdf(long long ql, long long qr, long long v) {
    mdf(rt, ql, qr, 1, n, v);
  }
  ll qry(long long p, long long ql, long long qr, long long l, long long r) {
    if (ql <= l && r <= qr) {
      return sum[p];
    }
    down(p);
    long long mid = l + r >> 1;
    ll ans = 0;
    if (ql <= mid) ans += qry(ls[p], ql, qr, l, mid);
    if (qr > mid) ans += qry(rs[p], ql, qr, mid + 1, r);
    return ans;
  }
  long long qry(long long ql, long long qr) { return qry(rt, ql, qr, 1, n); }
  ll qry(long long p, long long x, long long l, long long r) {
    if (l == r) {
      return tag[p];
    }
    down(p);
    long long mid = l + r >> 1;
    if (x <= mid)
      return qry(ls[p], x, l, mid);
    else
      return qry(rs[p], x, mid + 1, r);
  }
  ll qry(long long x) { return qry(rt, x, 1, n); }
} smt;
struct BIT {
  long long n;
  vector<ll> c;
  void init(long long _n) {
    n = _n + 1;
    c.resize(n + 1);
  }
  long long low(long long x) { return x & -x; }
  void u(long long x, long long y) {
    for (; x <= n; x += low(x)) c[x] += y;
  }
  ll q(long long x) {
    ll ans = 0;
    for (; x; x ^= low(x)) ans += c[x];
    return ans;
  }
  ll qry(long long x) { return q(x); }
  ll qry(long long l, long long r) {
    if (l > r) return 0;
    return q(r) - q(l - 1);
  }
} al[2], pt[2];
long long pos[maxn], rev[maxn];
struct suffixautomaton {
  long long ch[maxn][26], fa[maxn], len[maxn];
  long long las, cnt;
  suffixautomaton() { las = cnt = 1; }
  void ins(long long c, long long id) {
    long long p = las, np = las = ++cnt;
    pos[np] = id;
    len[np] = len[p] + 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) {
      fa[np] = 1;
    } else {
      long long q = ch[p][c];
      if (len[q] == len[p] + 1) {
        fa[np] = q;
      } else {
        long long nq = ++cnt;
        len[nq] = len[p] + 1;
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
      }
    }
  }
} sam;
long long n, t, len;
char s[maxn];
long long dep[maxn], f[maxn][22];
vector<long long> g[maxn];
long long ql[maxn], qr[maxn], from[maxn];
long long sz[maxn], fa[maxn], son[maxn];
void dfs(long long u) {
  sz[u] = 1;
  for (long long v : g[u]) {
    if (v ^ fa[u]) {
      fa[v] = u, dfs(v), sz[u] += sz[v];
      if (sz[v] > sz[son[u]]) son[u] = v;
    }
  }
}
long long top[maxn], dfn[maxn];
long long idx = 0;
void dfs(long long u, long long t) {
  top[u] = t, dfn[u] = ++idx;
  if (son[u]) dfs(son[u], t);
  for (long long v : g[u])
    if (!top[v]) dfs(v, v);
}
ll ans[maxn];
void Scanninglinefir() {
  static long long tmp[maxn];
  for (long long i = 1; i <= n; i++) {
    tmp[dfn[i]] = dep[i] - dep[fa[i]];
  }
  smt.init(n, tmp);
  static vector<pair<pair<long long, long long>, long long>> q[maxn];
  for (long long i = 1; i <= t; i++) {
    q[ql[i]].push_back(make_pair(make_pair(from[i], qr[i] - ql[i] + 1), i));
  }
  for (long long i = 1; i <= len; i++) {
    auto query = [&](pair<long long, long long> x) {
      ll ans = 1ll * (x.second - dep[fa[x.first]]) * smt.qry(dfn[x.first]);
      long long pos = fa[x.first];
      while (pos) {
        ans += smt.qry(dfn[top[pos]], dfn[pos]), pos = fa[top[pos]];
      }
      return ans;
    };
    for (auto x : q[i]) {
      ans[x.second] -= query(x.first);
    }
    long long pos = rev[i];
    while (pos) {
      smt.mdf(dfn[top[pos]], dfn[pos], 1), pos = fa[top[pos]];
    }
  }
}
void Scanninglinesec() {
  static vector<pair<long long, long long>> mdf[maxn];
  static vector<pair<pair<long long, long long>, long long>> qry[maxn];
  for (long long i = 1; i <= len; i++) {
    long long pos = rev[i];
    while (pos) {
      mdf[top[pos]].emplace_back(dep[pos], i), pos = fa[top[pos]];
    }
  }
  for (long long i = 1; i <= t; i++) {
    long long pos = from[i];
    while (pos) {
      if (pos == from[i]) {
        qry[top[pos]].emplace_back(make_pair(qr[i] - ql[i] + 1, qr[i] + 1), i);
      } else {
        qry[top[pos]].emplace_back(make_pair(dep[pos], qr[i] + 1), i);
      }
      pos = fa[top[pos]];
    }
  }
  al[0].init(len * 2 + 2), al[1].init(len * 2 + 2);
  pt[0].init(len * 2 + 2), pt[1].init(len * 2 + 2);
  for (long long i = 1; i <= n; i++) {
    if (top[i] != i) {
      continue;
    }
    long long st = dep[fa[i]] + 1;
    sort(mdf[i].begin(), mdf[i].end()), reverse(mdf[i].begin(), mdf[i].end());
    sort(qry[i].begin(), qry[i].end()), reverse(qry[i].begin(), qry[i].end());
    vector<pair<long long, long long>> bak = mdf[i];
    for (auto x : bak) {
      al[0].u(x.second, x.second), al[1].u(x.second, 1);
    }
    while (!mdf[i].empty() || !qry[i].empty()) {
      if (mdf[i].empty() || (!qry[i].empty() && qry[i].back().first.first <=
                                                    mdf[i].back().first)) {
        pair<long long, long long> x = qry[i].back().first;
        long long pos = qry[i].back().second;
        ans[pos] += 1ll * pt[1].qry(x.second) * x.second + pt[0].qry(x.second);
        long long tmp = x.second - x.first;
        if (tmp >= 1) {
          ans[pos] += al[1].qry(1, tmp) * (x.first - st + 1);
        }
        tmp = max(tmp, 0ll);
        ans[pos] +=
            1ll * al[1].qry(tmp + 1, x.second - st) * (x.second - st + 1) -
            al[0].qry(tmp + 1, x.second - st);
        qry[i].pop_back();
      } else {
        pair<long long, long long> x = mdf[i].back();
        al[0].u(x.second, -x.second), al[1].u(x.second, -1);
        pt[0].u(st + x.second, -(st + x.second - 1));
        pt[0].u(x.first + x.second + 1, st + x.second - 1 + x.first - st + 1);
        pt[1].u(st + x.second, 1), pt[1].u(x.first + x.second + 1, -1);
        mdf[i].pop_back();
      }
    }
    for (auto x : bak) {
      pt[0].u(st + x.second, st + x.second - 1);
      pt[0].u(x.first + x.second + 1, -(st + x.second - 1 + x.first - st + 1));
      pt[1].u(st + x.second, -1), pt[1].u(x.first + x.second + 1, 1);
    }
  }
}
signed main() {
  scanf("%s", s + 1);
  len = strlen(s + 1);
  for (long long i = len; i; i--) {
    sam.ins(s[i] - 'a', i);
  }
  n = sam.cnt;
  for (long long i = 1; i <= n; i++) {
    dep[i] = sam.len[i];
    if (pos[i]) rev[pos[i]] = i;
  }
  for (long long i = 2; i <= n; i++) {
    g[sam.fa[i]].push_back(i);
  }
  dfs(1), dfs(1, 1);
  scanf("%lld", &t);
  for (long long i = 1; i <= t; i++) {
    long long l, r;
    scanf("%lld %lld", &l, &r);
    ql[i] = l, qr[i] = r;
  }
  for (long long i = 1; i <= n; i++) {
    f[i][0] = sam.fa[i];
  }
  for (long long j = 1; j <= 20; j++)
    for (long long i = 1; i <= n; i++) f[i][j] = f[f[i][j - 1]][j - 1];
  for (long long i = 1; i <= t; i++) {
    long long l = ql[i], r = qr[i], goal = r - l + 1, p = rev[l];
    for (long long j = 20; ~j; --j)
      if (f[p][j] && dep[f[p][j]] >= goal) p = f[p][j];
    from[i] = p;
  }
  Scanninglinefir(), Scanninglinesec();
  for (long long i = 1; i <= t; i++) printf("%lld\n", ans[i]);
  return 0;
}