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;
template <typename T>
bool get_int(T &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-' && t != EOF; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  if (t == EOF) return false;
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
  return true;
}
template <typename T>
void print_int(T x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const double pi = acos(-1.0);
const int maxn = 400111;
int fa[maxn], val[maxn], tot;
namespace sam {
int go[maxn][26];
int append(int p, int c) {
  int np = ++tot;
  val[np] = val[p] + 1;
  while (p && !go[p][c]) {
    go[p][c] = np;
    p = fa[p];
  }
  if (!p)
    fa[np] = 1;
  else {
    int q = go[p][c];
    if (val[q] == val[p] + 1)
      fa[np] = q;
    else {
      int nq = ++tot;
      val[nq] = val[p] + 1;
      memcpy(go[nq], go[q], sizeof(go[q]));
      fa[nq] = fa[q];
      fa[np] = fa[q] = nq;
      while (p && go[p][c] == q) {
        go[p][c] = nq;
        p = fa[p];
      }
    }
  }
  return np;
}
void construct(char *s, int n, int *pos) {
  tot = 1;
  pos[n + 1] = 1;
  for (int i = n; i >= 1; i--) pos[i] = append(pos[i + 1], s[i] - 'a');
}
};  // namespace sam
vector<int> g[maxn], qs[maxn];
int sz[maxn], son[maxn], top[maxn];
void dfs1(int x) {
  sz[x] = 1;
  for (int i = 0; i < (int)g[x].size(); i++) {
    dfs1(g[x][i]);
    sz[x] += sz[g[x][i]];
    if (sz[son[x]] < sz[g[x][i]]) son[x] = g[x][i];
  }
  if (x == 1) son[x] = 0;
}
void dfs2(int x, int tp) {
  top[x] = tp;
  if (son[x]) dfs2(son[x], tp);
  for (int i = 0; i < (int)g[x].size(); i++)
    if (g[x][i] != son[x]) dfs2(g[x][i], g[x][i]);
}
struct q_t {
  int l, r, v, id;
  q_t(int k1, int k2, int k3, int k4) {
    l = k1;
    r = k2;
    v = k3;
    id = k4;
  }
};
vector<q_t> q_rec[maxn], q_tri[maxn];
int pos[200111];
void addquery(int l, int r, int id) {
  int cur = pos[l], len = r - l + 1;
  while (cur) {
    int tp = val[fa[top[cur]]];
    if (tp < len) {
      q_rec[top[cur]].push_back(
          q_t(l, r - min(val[cur], len), min(val[cur], len) - tp, id));
      q_tri[top[cur]].push_back(q_t(r - min(val[cur], len) + 1, r - tp, 0, id));
    }
    cur = fa[top[cur]];
  }
}
struct BIT {
  long long bit[maxn];
  BIT() { memset(bit, 0, sizeof(bit)); }
  void add(int x, int v) {
    for (; x < maxn; x += x & -x) bit[x] += v;
  }
  long long query(int x) {
    long long ret = 0;
    for (; x; x -= x & -x) ret += bit[x];
    return ret;
  }
};
long long ans[200111];
int have[maxn];
pair<int, int> vs[maxn];
void addall(int x, int ban, int t) {
  if (have[x]) vs[++tot] = make_pair(have[x], t);
  for (int i = 0; i < (int)g[x].size(); i++)
    if (g[x][i] != ban) addall(g[x][i], ban, t);
}
BIT in, out_cnt, out_sum;
void go(int tp) {
  tot = 0;
  int cur = tp;
  for (int i = 1; cur; i++) {
    addall(cur, son[cur], val[cur] - val[fa[tp]]);
    cur = son[cur];
  }
  vector<pair<int, int> > qv;
  for (int i = 1; i <= tot; i++) qv.push_back(make_pair(vs[i].second, -i));
  for (int i = 0; i < (int)q_rec[tp].size(); i++) {
    qv.push_back(make_pair(q_rec[tp][i].v, i));
  }
  sort(qv.begin(), qv.end());
  for (int i = 1; i <= tot; i++) out_cnt.add(vs[i].first, 1);
  for (int i = 0; i < (int)qv.size(); i++) {
    int id = qv[i].second;
    if (id < 0) {
      id = -id;
      out_cnt.add(vs[id].first, -1);
      in.add(vs[id].first, vs[id].second);
    } else {
      q_t &cur = q_rec[tp][id];
      ans[cur.id] += in.query(cur.r) - in.query(cur.l - 1) +
                     (out_cnt.query(cur.r) - out_cnt.query(cur.l - 1)) * cur.v;
    }
  }
  for (int i = 1; i <= tot; i++) in.add(vs[i].first, -vs[i].second);
  qv.clear();
  for (int i = 1; i <= tot; i++)
    qv.push_back(make_pair(vs[i].first + vs[i].second, -i));
  for (int i = 0; i < (int)q_tri[tp].size(); i++) {
    qv.push_back(make_pair(q_tri[tp][i].r + 1, i));
  }
  sort(qv.begin(), qv.end());
  for (int i = 1; i <= tot; i++) {
    out_cnt.add(vs[i].first, 1);
    out_sum.add(vs[i].first, vs[i].first);
  }
  for (int i = 0; i < (int)qv.size(); i++) {
    int id = qv[i].second;
    if (id < 0) {
      id = -id;
      out_cnt.add(vs[id].first, -1);
      out_sum.add(vs[id].first, -vs[id].first);
      in.add(vs[id].first, vs[id].second);
    } else {
      q_t &cur = q_tri[tp][id];
      ans[cur.id] +=
          in.query(cur.r) - in.query(cur.l - 1) +
          (out_cnt.query(cur.r) - out_cnt.query(cur.l - 1)) * (cur.r + 1) -
          (out_sum.query(cur.r) - out_sum.query(cur.l - 1));
    }
  }
  for (int i = 1; i <= tot; i++) in.add(vs[i].first, -vs[i].second);
}
void dfs(int x) {
  for (int i = 0; i < (int)g[x].size(); i++) dfs(g[x][i]);
  if (top[x] == x && x > 1) go(x);
}
char s[200111];
int n, q, ql[200111], qr[200111];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  get_int(q);
  for (int i = 1; i <= q; i++) (get_int(ql[i]) && get_int(qr[i]));
  sam::construct(s, n, pos);
  for (int i = 2; i <= tot; i++) g[fa[i]].push_back(i);
  for (int i = 1; i <= n; i++) have[pos[i]] = i;
  dfs1(1);
  dfs2(1, 1);
  for (int i = 1; i <= q; i++) addquery(ql[i], qr[i], i);
  dfs(1);
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}