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;
struct Node {
  int t[26], f, len, p, tf;
} a[200500 << 1];
int tn, las;
void ins(int c) {
  int p = las, np = ++tn;
  las = np;
  a[np].len = a[p].len + 1;
  for (; p && !a[p].t[c]; p = a[p].f) a[p].t[c] = np;
  if (!p)
    a[np].f = 1;
  else {
    int v = a[p].t[c];
    if (a[v].len == a[p].len + 1)
      a[np].f = v;
    else {
      int nv = ++tn;
      a[nv] = a[v];
      a[nv].len = a[p].len + 1;
      for (; p && a[p].t[c] == v; p = a[p].f) a[p].t[c] = nv;
      a[np].f = a[v].f = nv;
    }
  }
}
vector<int> g[200500 << 1];
int ed[200500 << 1], td[200500], in[200500 << 1], tim, siz[200500 << 1];
void pfs1(int u) {
  siz[u] = 1;
  for (int i = 0, v; i < g[u].size(); i++) {
    pfs1(v = g[u][i]);
    siz[u] += siz[v];
    if (siz[v] > siz[a[u].p]) a[u].p = v;
  }
}
void pfs2(int u, int tf) {
  a[u].tf = tf;
  in[u] = ++tim;
  if (a[u].p) {
    pfs2(a[u].p, tf);
    for (int i = 0; i < g[u].size(); i++)
      if (a[u].p != g[u][i]) pfs2(g[u][i], g[u][i]);
  }
}
int wfl, wfr, wfd;
struct SGT {
  struct SGT_Node {
    long long s, len;
    int tg;
    inline void ladd(int t) {
      tg += t;
      s += len * t;
    }
  } a[200500 << 3];
  int dl[200500 << 1], dr[200500 << 1];
  void build(int l, int r, int u) {
    if (l == r) {
      a[u].len = dr[l] - dl[l] + 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, u << 1);
    build(mid + 1, r, u << 1 | 1);
    a[u].len = a[u << 1].len + a[u << 1 | 1].len;
  }
  inline void ladd(int u) {
    if (a[u].tg) {
      a[u << 1].ladd(a[u].tg);
      a[u << 1 | 1].ladd(a[u].tg);
      a[u].tg = 0;
    }
  }
  void add(int l, int r, int u) {
    if (wfl <= l && r <= wfr) {
      a[u].ladd(1);
      return;
    }
    int mid = (l + r) >> 1;
    ladd(u);
    if (wfl <= mid) add(l, mid, u << 1);
    if (mid < wfr) add(mid + 1, r, u << 1 | 1);
    a[u].s = a[u << 1].s + a[u << 1 | 1].s;
  }
  int qryp(int l, int r, int u) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    ladd(u);
    if (wfr <= mid) return qryp(l, mid, u << 1);
    if (mid < wfl) return qryp(mid + 1, r, u << 1 | 1);
    if (wfd >= dl[mid + 1]) return qryp(mid + 1, r, u << 1 | 1);
    return qryp(l, mid, u << 1);
  }
  long long qrys(int l, int r, int u) {
    if (wfl <= l && r <= wfr) return a[u].s;
    int mid = (l + r) >> 1;
    long long ret = 0;
    ladd(u);
    if (wfl <= mid) ret = qrys(l, mid, u << 1);
    if (mid < wfr) ret += qrys(mid + 1, r, u << 1 | 1);
    return ret;
  }
  void add(int l, int r) {
    wfl = l;
    wfr = r;
    add(1, tn, 1);
  }
  int qryp(int l, int r) {
    wfl = l;
    wfr = r;
    return qryp(1, tn, 1);
  }
  long long qrys(int l, int r) {
    wfl = l;
    wfr = r;
    return qrys(1, tn, 1);
  }
} S;
void padd(int u) {
  while (u) {
    S.add(in[a[u].tf], in[u]);
    u = a[a[u].tf].f;
  }
}
long long pqry(int u) {
  long long ret = 0;
  while (u) {
    if (a[a[a[u].tf].f].len < wfd) {
      if (a[u].len <= wfd)
        ret += S.qrys(in[a[u].tf], in[u]);
      else {
        int p = S.qryp(in[a[u].tf], in[u]);
        long long s0 = 0, s1 = 0;
        if (in[a[u].tf] < p) s0 = S.qrys(in[a[u].tf], p - 1);
        s1 = S.qrys(p, p);
        ret += s0 + s1 / (S.dr[p] - S.dl[p] + 1) *
                        max(0, min(S.dr[p], wfd) - S.dl[p] + 1);
      }
    }
    u = a[a[u].tf].f;
  }
  return ret;
}
struct BIT {
  long long t[200500 << 2];
  int l, n;
  void add(int p, int x) {
    p -= l;
    while (p <= n) {
      t[p] += x;
      p += ((p) & -(p));
    }
  }
  long long qry(int p) {
    long long ret = 0;
    p -= l;
    while (p) {
      ret += t[p];
      p ^= ((p) & -(p));
    }
    return ret;
  }
} Tc, Tx;
struct Data {
  int x, y, p;
} p[200500 << 1];
bool cmp(const Data A, const Data B) { return A.x < B.x; }
vector<Data> b[200500 << 1], b2[200500];
void adq(int u, int r, int i, int lim) {
  while (u) {
    b[a[u].tf].push_back((Data){min(a[u].len, lim) + 1, r + 1, i});
    u = a[a[u].tf].f;
  }
}
int n, tot, fl, fl2;
void dfs(int u) {
  if (ed[u]) {
    p[++tot] = (Data){fl + 1, ed[u] + fl + 1, -1};
    p[++tot] = (Data){fl2 + 1, ed[u] + fl2 + 1, 1};
  }
  for (int i = 0; i < g[u].size(); i++) dfs(g[u][i]);
}
long long ans[200500];
void calc(vector<Data> &b) {
  int tp = 1;
  for (int i = 0; i < b.size(); i++) {
    Data q = b[i];
    while (tp <= tot && p[tp].x <= q.x) {
      int to = p[tp].y - p[tp].x;
      Tx.add(to, p[tp].p * p[tp].x);
      Tc.add(to, p[tp].p);
      tp++;
    }
    int l = -n * 2, r = q.y - q.x;
    ans[q.p] +=
        1ll * (Tc.qry(r) - Tc.qry(l - 1)) * q.x - (Tx.qry(r) - Tx.qry(l - 1));
  }
  for (int i = 1; i < tp; i++) {
    int to = p[i].y - p[i].x;
    Tx.add(to, -p[i].p * p[i].x);
    Tc.add(to, -p[i].p);
  }
}
void solve(int u) {
  int v = u;
  fl2 = a[a[u].f].len;
  tot = 0;
  while (v) {
    fl = a[v].len;
    if (ed[v]) {
      p[++tot] = (Data){fl + 1, ed[v] + fl + 1, -1};
      p[++tot] = (Data){fl2 + 1, ed[v] + fl2 + 1, 1};
    }
    for (int i = 0; i < g[v].size(); i++)
      if (g[v][i] != a[v].p) dfs(g[v][i]);
    v = a[v].p;
  }
  sort(p + 1, p + tot + 1, cmp);
  sort(b[u].begin(), b[u].end(), cmp);
  calc(b[u]);
  for (int i = 1; i <= tot; i++) swap(p[i].x, p[i].y);
  for (int i = 0; i < b[u].size(); i++) {
    swap(b[u][i].x, b[u][i].y);
    b[u][i].y--;
  }
  sort(p + 1, p + tot + 1, cmp);
  sort(b[u].begin(), b[u].end(), cmp);
  calc(b[u]);
}
int q, lf[200500];
char str[200500];
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  las = tn = 1;
  for (int i = n; i; i--) ins(str[i] - 'a');
  for (int i = n, p = 1; i; i--) {
    p = a[p].t[str[i] - 'a'];
    ed[td[i] = p] = i;
  }
  for (int i = 2; i <= tn; i++) g[a[i].f].push_back(i);
  pfs1(1);
  pfs2(1, 1);
  scanf("%d", &q);
  for (int i = 1, l, r; i <= q; i++) {
    scanf("%d%d", &l, &r);
    adq(td[l], r + 1, i, r - l + 1);
    b2[l].push_back((Data){l, r, i});
  }
  Tc.l = Tx.l = -n * 2 - 1;
  Tc.n = Tx.n = n * 4 + 1;
  for (int i = 1; i <= tn; i++)
    if (a[i].tf == i) solve(i);
  for (int i = 1; i <= tn; i++) {
    S.dl[in[i]] = a[a[i].f].len + 1;
    S.dr[in[i]] = a[i].len;
  }
  S.build(1, tn, 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < b2[i].size(); j++) {
      wfd = b2[i][j].y - i + 1;
      ans[b2[i][j].p] -= pqry(td[i]);
    }
    padd(td[i]);
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}