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 = 4e5 + 100;
const int D = 19;
struct QUE {
  int l, r, len, id;
  QUE(int _l, int _r, int _len, int _id) {
    l = _l;
    r = _r;
    len = _len;
    id = _id;
  }
};
struct OPT {
  int x, y;
  OPT(int _x, int _y) {
    x = _x;
    y = _y;
  }
};
bool cmpx(OPT &a, OPT &b) { return a.x < b.x; }
bool cmpy(OPT &a, OPT &b) { return a.x + a.y < b.x + b.y; }
bool cmpl(QUE &a, QUE &b) { return a.l < b.l; }
bool cmpr(QUE &a, QUE &b) { return a.r < b.r; }
struct BIT {
  long long bit[N] =
      {
          0,
  },
            n;
  void add(int x, int v) {
    while (x <= n) {
      bit[x] += v;
      x += x & -x;
    }
  }
  long long sum(int x) {
    long long s = 0;
    while (x) {
      s += bit[x];
      x -= x & -x;
    }
    return s;
  }
} b1, b2;
struct SAM {
  int next[N][26], fa[N], len[N], pos[N], n;
  int root, tot, last;
  vector<int> g[N];
  vector<QUE> q[N];
  vector<OPT> p[N];
  long long ans[N];
  int newnode(int l) {
    fa[tot] = -1;
    for (int i = 0; i < 26; ++i) next[tot][i] = -1;
    len[tot++] = l;
    return tot - 1;
  }
  void init() {
    tot = 0;
    last = root = newnode(0);
  }
  void extend(int x, int ep) {
    int p = last;
    int cur = newnode(len[p] + 1);
    while (p != -1 && next[p][x] == -1) {
      next[p][x] = cur;
      p = fa[p];
    }
    if (p == -1)
      fa[cur] = root;
    else {
      int q = next[p][x];
      if (len[q] == len[p] + 1)
        fa[cur] = q;
      else {
        int tmp = newnode(len[p] + 1);
        memcpy(next[tmp], next[q], sizeof(next[q]));
        fa[tmp] = fa[q];
        fa[q] = fa[cur] = tmp;
        while (p != -1 && next[p][x] == q) {
          next[p][x] = tmp;
          p = fa[p];
        }
      }
    }
    last = cur;
    pos[ep] = last;
  }
  int top[N], son[N], siz[N], par[N][D];
  void dfs1(int u) {
    for (int i = 1; i < D; ++i) par[u][i] = par[par[u][i - 1]][i - 1];
    son[u] = -1;
    siz[u] = 1;
    for (auto v : g[u]) {
      dfs1(v);
      siz[u] += siz[v];
      if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
    }
  }
  void dfs2(int u, int t) {
    top[u] = t;
    if (~son[u]) dfs2(son[u], t);
    for (auto v : g[u])
      if (v != son[u]) dfs2(v, v);
  }
  void build() {
    for (int i = 0; i < tot; ++i) g[i].clear();
    for (int i = 1; i < tot; ++i) g[fa[i]].push_back(i);
    for (int i = 0; i < tot; ++i) par[i][0] = fa[i];
    for (auto v : g[0]) dfs1(v), dfs2(v, v);
  }
  int getpos(int l, int r) {
    r = r - l + 1;
    l = pos[l];
    for (int i = D - 1; i >= 0; --i)
      if (len[par[l][i]] >= r) l = par[l][i];
    return l;
  }
  void addque(int l, int r, int id) {
    int tp = r - l + 1, now = getpos(l, r);
    int up = top[now];
    while (now) {
      q[up].push_back(QUE(l, r, min(len[now], tp) - len[fa[up]], id));
      tp -= min(len[now], tp) - len[fa[up]];
      now = fa[up];
      up = top[now];
    }
  }
  void addopt(int l) {
    int tp = n - l + 1, now = pos[l];
    int up = top[now];
    while (now) {
      p[up].push_back(
          OPT(l + len[fa[up]] + 1, min(len[now], tp) - len[fa[up]]));
      tp -= min(len[now], tp) - len[fa[up]];
      now = fa[up];
      up = top[now];
    }
  }
  void solve() {
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i < tot; ++i)
      if (top[i] == i) {
        get(p[i], q[i], len[fa[i]] + 1);
      }
  }
  void get(vector<OPT> &p, vector<QUE> &q, int tp) {
    int i, j;
    sort(p.begin(), p.end(), cmpy);
    sort(q.begin(), q.end(), cmpr);
    for (i = 0, j = 0; i < q.size(); ++i) {
      while (j < p.size() && p[j].x + p[j].y <= q[i].r + 2) {
        b1.add(p[j].y, 1);
        b2.add(p[j].y, p[j].y);
        j++;
      }
      ans[q[i].id] +=
          1LL * q[i].len * (j - b1.sum(q[i].len)) + b2.sum(q[i].len);
    }
    while (j--) {
      b1.add(p[j].y, -1);
      b2.add(p[j].y, -p[j].y);
    }
    reverse(p.begin(), p.end());
    reverse(q.begin(), q.end());
    for (i = 0, j = 0; i < q.size(); ++i) {
      while (j < p.size() && p[j].x + p[j].y > q[i].r + 2) {
        b1.add(b1.n - p[j].x, 1);
        b2.add(b2.n - p[j].x, p[j].x);
        j++;
      }
      int c1 = b1.sum(b1.n - q[i].r - 2 + q[i].len),
          c2 = b1.sum(b2.n - q[i].r - 2);
      ans[q[i].id] += 1LL * (j - c1) * q[i].len;
      ans[q[i].id] +=
          1LL * (c1 - c2) * (q[i].r + 2) -
          (b2.sum(b2.n - q[i].r - 2 + q[i].len) - b2.sum(b2.n - q[i].r - 2));
    }
    while (j--) {
      b1.add(b1.n - p[j].x, -1);
      b2.add(b2.n - p[j].x, -p[j].x);
    }
    for (i = 0; i < p.size(); ++i) p[i].x -= tp;
    sort(p.begin(), p.end(), cmpx);
    sort(q.begin(), q.end(), cmpl);
    for (i = 0, j = 0; i < q.size(); ++i) {
      while (j < p.size() && p[j].x < q[i].l) {
        b1.add(p[j].y, 1);
        b2.add(p[j].y, p[j].y);
        j++;
      }
      ans[q[i].id] -=
          1LL * (j - b1.sum(q[i].len)) * q[i].len + b2.sum(q[i].len);
    }
    while (j--) {
      b1.add(p[j].y, -1);
      b2.add(p[j].y, -p[j].y);
    }
  }
} sam;
char s[N];
int n, m;
int l[N], r[N];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  sam.init();
  for (int i = n; i >= 1; --i) sam.extend(s[i] - 'a', i);
  sam.build();
  b1.n = b2.n = 2 * n + 2;
  sam.n = n;
  for (int i = 1; i <= n; ++i) sam.addopt(i);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d %d", &l[i], &r[i]);
    sam.addque(l[i], r[i], i);
  }
  sam.solve();
  for (int i = 1; i <= m; ++i) printf("%lld\n", sam.ans[i]);
}