#include <bits/stdc++.h>
using namespace std;
const int maxN = 4e5 + 10;
struct SAM {
  int pa, len;
  int trans[26];
} st[maxN + 1];
struct Que {
  int l, r, len, id;
  Que(int L = 0, int R = 0, int LEN = 0, int ID = 0) {
    l = L, r = R, len = LEN, id = ID;
  }
};
struct Node {
  int x, len;
  Node(int X = 0, int LEN = 0) {
    x = X;
    len = LEN;
  }
};
struct Query {
  int a, b, id;
  Query(int A = 0, int B = 0, int ID = 0) { a = A, b = B, id = ID; }
};
int n, m, cnt, lst, lim;
int dfn[maxN + 1], ct, sz[maxN + 1], wson[maxN + 1];
int dep[maxN + 1], top[maxN + 1], fa[maxN + 1][21];
int p[maxN + 1], lg[maxN + 1];
long long ans[maxN + 1];
char s[maxN + 1];
vector<int> son[maxN + 1];
vector<Que> q[maxN + 1];
vector<Node> vec[maxN + 1];
int T;
struct SegmentTree {
  struct Node {
    int clk;
    long long sum, tag;
  } tree[maxN * 4 + 1];
  void clear(int node) {
    if (tree[node].clk == T) return;
    tree[node].clk = T;
    tree[node].sum = tree[node].tag = 0;
  }
  void pushup(int node) {
    clear(node << 1), clear(node << 1 | 1);
    tree[node].sum = tree[node << 1].sum + tree[node << 1 | 1].sum;
  }
  void pushdown(int node, int l, int r) {
    clear(node << 1), clear(node << 1 | 1);
    if (!tree[node].tag) return;
    int mid = (l + r) >> 1, v = tree[node].tag;
    tree[node << 1].sum += 1ll * v * (mid - l + 1), tree[node << 1].tag += v;
    tree[node << 1 | 1].sum += 1ll * v * (r - mid),
        tree[node << 1 | 1].tag += v;
    tree[node].tag = 0;
  }
  void change(int node, int l, int r, int x, int y, int v) {
    if (x > y) return;
    clear(node);
    if (x <= l && r <= y) {
      tree[node].sum += 1ll * v * (r - l + 1);
      tree[node].tag += v;
      return;
    }
    pushdown(node, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) change(node << 1, l, mid, x, y, v);
    if (y > mid) change(node << 1 | 1, mid + 1, r, x, y, v);
    pushup(node);
  }
  long long query(int node, int l, int r, int x, int y) {
    if (x > y) return 0;
    clear(node);
    if (x <= l && r <= y) return tree[node].sum;
    pushdown(node, l, r);
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (x <= mid) ans += query(node << 1, l, mid, x, y);
    if (y > mid) ans += query(node << 1 | 1, mid + 1, r, x, y);
    return ans;
  }
} T0;
struct BIT {
  long long C[maxN + 1];
  int lowbit(int x) { return x & -x; }
  void change(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) C[i] += v;
  }
  long long query(int x) {
    long long ans = 0;
    for (int i = x; i; i ^= lowbit(i)) ans += C[i];
    return ans;
  }
  long long ask(int l, int r) {
    l = max(l, 1);
    r = min(n, r);
    return l > r ? 0 : query(r) - query(l - 1);
  }
} T1, T2, T3, T4;
inline int read() {
  int num = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
  return num * f;
}
inline void extend(int c) {
  int np = ++cnt, p = lst;
  st[np].len = st[p].len + 1;
  while (p && !st[p].trans[c]) st[p].trans[c] = np, p = st[p].pa;
  if (!p)
    st[np].pa = 1;
  else {
    int q = st[p].trans[c];
    if (st[q].len == st[p].len + 1)
      st[np].pa = q;
    else {
      int nq = ++cnt;
      st[nq] = st[q];
      st[nq].len = st[p].len + 1;
      st[np].pa = st[q].pa = nq;
      while (p && st[p].trans[c] == q) st[p].trans[c] = nq, p = st[p].pa;
    }
  }
  lst = np;
}
inline void dfs1(int u, int pa) {
  dep[u] = dep[pa] + 1;
  fa[u][0] = pa;
  sz[u] = 1;
  for (int i = 1; (1 << i) <= dep[u]; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (auto v : son[u]) {
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[wson[u]]) wson[u] = v;
  }
}
inline void dfs2(int u, int tp) {
  top[u] = tp;
  dfn[u] = ++ct;
  if (wson[u]) dfs2(wson[u], tp);
  for (auto v : son[u]) {
    if (v == wson[u]) continue;
    dfs2(v, v);
  }
}
inline int get(int l, int r) {
  int x = p[l], len = r - l + 1;
  for (int i = lg[dep[x]]; i >= 0; i--)
    if (st[fa[x][i]].len >= len) x = fa[x][i];
  return x;
}
inline bool cmp(Query a, Query b) {
  return a.a == b.a ? a.id < b.id : a.a < b.a;
}
inline void solve(int rt) {
  int mn = st[fa[rt][0]].len + 1;
  vector<Query> A;
  for (auto now : vec[rt]) {
    T1.change(now.x, 1);
    A.push_back(Query(now.len, now.x, 0));
  }
  for (auto now : q[rt]) A.push_back(Query(now.len, now.l - 1, now.id));
  sort(A.begin(), A.end(), cmp);
  for (auto now : A)
    if (!now.id)
      T1.change(now.b, -1), T2.change(now.b, now.a);
    else
      ans[now.id] -= T1.query(now.b) * now.a + T2.query(now.b);
  for (auto now : A)
    if (!now.id) T2.change(now.b, -now.a);
  A.clear();
  T++;
  for (auto now : vec[rt]) {
    T3.change(now.x + mn - 1, now.x + mn - 1);
    T4.change(now.x + mn - 1, 1);
    A.push_back(Query(now.len, now.x + mn - 1, 0));
  }
  for (auto now : q[rt]) A.push_back(Query(now.len, now.r + 1, now.id));
  sort(A.begin(), A.end(), cmp);
  for (auto now : A)
    if (!now.id) {
      T0.change(1, 1, lim, now.b + 1, now.b + now.a, 1);
      T3.change(now.b, -now.b);
      T4.change(now.b, -1);
    } else {
      ans[now.id] += T0.query(1, 1, lim, 1, now.b);
      ans[now.id] += 1ll * now.a * T4.ask(1, now.b);
      int ct = T4.ask(now.b - now.a, now.b);
      ans[now.id] -=
          T3.ask(now.b - now.a, now.b) + 1ll * ct * now.a - 1ll * ct * now.b;
    }
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  lim = 2 * n;
  lst = cnt = 1;
  for (int i = n; i >= 1; i--) extend(s[i] - 'a'), p[i] = lst;
  for (int i = 2; i <= cnt; i++) son[st[i].pa].push_back(i);
  dfs1(1, 0);
  dfs2(1, 1);
  for (int i = 2; i <= cnt; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; i++) {
    int u = p[i];
    while (u) {
      if (st[u].len)
        vec[top[u]].push_back(Node(i, st[u].len - st[fa[top[u]][0]].len));
      u = fa[top[u]][0];
    }
  }
  m = read();
  for (int i = 1; i <= m; i++) {
    int l = read(), r = read();
    int u = get(l, r);
    while (u) {
      int len = min(r - l + 1, st[u].len) - st[fa[top[u]][0]].len;
      if (len) q[top[u]].push_back(Que(l, r, len, i));
      u = fa[top[u]][0];
    }
  }
  for (int i = 1; i <= cnt; i++)
    if (top[i] == i) solve(i);
  for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
  return 0;
}

### Prompt

In cpp, your task is to solve the following 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. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxN = 4e5 + 10;
struct SAM {
  int pa, len;
  int trans[26];
} st[maxN + 1];
struct Que {
  int l, r, len, id;
  Que(int L = 0, int R = 0, int LEN = 0, int ID = 0) {
    l = L, r = R, len = LEN, id = ID;
  }
};
struct Node {
  int x, len;
  Node(int X = 0, int LEN = 0) {
    x = X;
    len = LEN;
  }
};
struct Query {
  int a, b, id;
  Query(int A = 0, int B = 0, int ID = 0) { a = A, b = B, id = ID; }
};
int n, m, cnt, lst, lim;
int dfn[maxN + 1], ct, sz[maxN + 1], wson[maxN + 1];
int dep[maxN + 1], top[maxN + 1], fa[maxN + 1][21];
int p[maxN + 1], lg[maxN + 1];
long long ans[maxN + 1];
char s[maxN + 1];
vector<int> son[maxN + 1];
vector<Que> q[maxN + 1];
vector<Node> vec[maxN + 1];
int T;
struct SegmentTree {
  struct Node {
    int clk;
    long long sum, tag;
  } tree[maxN * 4 + 1];
  void clear(int node) {
    if (tree[node].clk == T) return;
    tree[node].clk = T;
    tree[node].sum = tree[node].tag = 0;
  }
  void pushup(int node) {
    clear(node << 1), clear(node << 1 | 1);
    tree[node].sum = tree[node << 1].sum + tree[node << 1 | 1].sum;
  }
  void pushdown(int node, int l, int r) {
    clear(node << 1), clear(node << 1 | 1);
    if (!tree[node].tag) return;
    int mid = (l + r) >> 1, v = tree[node].tag;
    tree[node << 1].sum += 1ll * v * (mid - l + 1), tree[node << 1].tag += v;
    tree[node << 1 | 1].sum += 1ll * v * (r - mid),
        tree[node << 1 | 1].tag += v;
    tree[node].tag = 0;
  }
  void change(int node, int l, int r, int x, int y, int v) {
    if (x > y) return;
    clear(node);
    if (x <= l && r <= y) {
      tree[node].sum += 1ll * v * (r - l + 1);
      tree[node].tag += v;
      return;
    }
    pushdown(node, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) change(node << 1, l, mid, x, y, v);
    if (y > mid) change(node << 1 | 1, mid + 1, r, x, y, v);
    pushup(node);
  }
  long long query(int node, int l, int r, int x, int y) {
    if (x > y) return 0;
    clear(node);
    if (x <= l && r <= y) return tree[node].sum;
    pushdown(node, l, r);
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (x <= mid) ans += query(node << 1, l, mid, x, y);
    if (y > mid) ans += query(node << 1 | 1, mid + 1, r, x, y);
    return ans;
  }
} T0;
struct BIT {
  long long C[maxN + 1];
  int lowbit(int x) { return x & -x; }
  void change(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) C[i] += v;
  }
  long long query(int x) {
    long long ans = 0;
    for (int i = x; i; i ^= lowbit(i)) ans += C[i];
    return ans;
  }
  long long ask(int l, int r) {
    l = max(l, 1);
    r = min(n, r);
    return l > r ? 0 : query(r) - query(l - 1);
  }
} T1, T2, T3, T4;
inline int read() {
  int num = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
  return num * f;
}
inline void extend(int c) {
  int np = ++cnt, p = lst;
  st[np].len = st[p].len + 1;
  while (p && !st[p].trans[c]) st[p].trans[c] = np, p = st[p].pa;
  if (!p)
    st[np].pa = 1;
  else {
    int q = st[p].trans[c];
    if (st[q].len == st[p].len + 1)
      st[np].pa = q;
    else {
      int nq = ++cnt;
      st[nq] = st[q];
      st[nq].len = st[p].len + 1;
      st[np].pa = st[q].pa = nq;
      while (p && st[p].trans[c] == q) st[p].trans[c] = nq, p = st[p].pa;
    }
  }
  lst = np;
}
inline void dfs1(int u, int pa) {
  dep[u] = dep[pa] + 1;
  fa[u][0] = pa;
  sz[u] = 1;
  for (int i = 1; (1 << i) <= dep[u]; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (auto v : son[u]) {
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[wson[u]]) wson[u] = v;
  }
}
inline void dfs2(int u, int tp) {
  top[u] = tp;
  dfn[u] = ++ct;
  if (wson[u]) dfs2(wson[u], tp);
  for (auto v : son[u]) {
    if (v == wson[u]) continue;
    dfs2(v, v);
  }
}
inline int get(int l, int r) {
  int x = p[l], len = r - l + 1;
  for (int i = lg[dep[x]]; i >= 0; i--)
    if (st[fa[x][i]].len >= len) x = fa[x][i];
  return x;
}
inline bool cmp(Query a, Query b) {
  return a.a == b.a ? a.id < b.id : a.a < b.a;
}
inline void solve(int rt) {
  int mn = st[fa[rt][0]].len + 1;
  vector<Query> A;
  for (auto now : vec[rt]) {
    T1.change(now.x, 1);
    A.push_back(Query(now.len, now.x, 0));
  }
  for (auto now : q[rt]) A.push_back(Query(now.len, now.l - 1, now.id));
  sort(A.begin(), A.end(), cmp);
  for (auto now : A)
    if (!now.id)
      T1.change(now.b, -1), T2.change(now.b, now.a);
    else
      ans[now.id] -= T1.query(now.b) * now.a + T2.query(now.b);
  for (auto now : A)
    if (!now.id) T2.change(now.b, -now.a);
  A.clear();
  T++;
  for (auto now : vec[rt]) {
    T3.change(now.x + mn - 1, now.x + mn - 1);
    T4.change(now.x + mn - 1, 1);
    A.push_back(Query(now.len, now.x + mn - 1, 0));
  }
  for (auto now : q[rt]) A.push_back(Query(now.len, now.r + 1, now.id));
  sort(A.begin(), A.end(), cmp);
  for (auto now : A)
    if (!now.id) {
      T0.change(1, 1, lim, now.b + 1, now.b + now.a, 1);
      T3.change(now.b, -now.b);
      T4.change(now.b, -1);
    } else {
      ans[now.id] += T0.query(1, 1, lim, 1, now.b);
      ans[now.id] += 1ll * now.a * T4.ask(1, now.b);
      int ct = T4.ask(now.b - now.a, now.b);
      ans[now.id] -=
          T3.ask(now.b - now.a, now.b) + 1ll * ct * now.a - 1ll * ct * now.b;
    }
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  lim = 2 * n;
  lst = cnt = 1;
  for (int i = n; i >= 1; i--) extend(s[i] - 'a'), p[i] = lst;
  for (int i = 2; i <= cnt; i++) son[st[i].pa].push_back(i);
  dfs1(1, 0);
  dfs2(1, 1);
  for (int i = 2; i <= cnt; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; i++) {
    int u = p[i];
    while (u) {
      if (st[u].len)
        vec[top[u]].push_back(Node(i, st[u].len - st[fa[top[u]][0]].len));
      u = fa[top[u]][0];
    }
  }
  m = read();
  for (int i = 1; i <= m; i++) {
    int l = read(), r = read();
    int u = get(l, r);
    while (u) {
      int len = min(r - l + 1, st[u].len) - st[fa[top[u]][0]].len;
      if (len) q[top[u]].push_back(Que(l, r, len, i));
      u = fa[top[u]][0];
    }
  }
  for (int i = 1; i <= cnt; i++)
    if (top[i] == i) solve(i);
  for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
  return 0;
}

```