#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
struct Sam {
  Sam *next[26], *par;
  int step, pos;
  int minLen() { return par ? par->step + 1 : 1; }
} pool[N], *root, *last;
int tot;
Sam *newnode(int step) {
  Sam *t = pool + (tot++);
  memset(t->next, 0, sizeof(t->next));
  t->par = NULL;
  t->step = step;
  t->pos = -1;
  return t;
}
void init() {
  tot = 0;
  last = root = newnode(0);
}
Sam *leaf[N / 2];
void Extend(int w, int pos) {
  Sam *p = last;
  Sam *newv = newnode(p->step + 1);
  newv->pos = pos;
  leaf[pos] = newv;
  for (; p && !p->next[w]; p = p->par) p->next[w] = newv;
  if (!p)
    newv->par = root;
  else {
    Sam *q = p->next[w];
    if (q->step == p->step + 1)
      newv->par = q;
    else {
      Sam *nq = newnode(p->step + 1);
      memcpy(nq->next, q->next, sizeof(q->next));
      nq->par = q->par;
      q->par = nq;
      newv->par = nq;
      for (; p && p->next[w] == q; p = p->par) p->next[w] = nq;
    }
  }
  last = newv;
}
char s[N / 2];
vector<int> G[N];
int sz[N], son[N], top[N];
void dfs1(int u) {
  sz[u] = 1;
  son[u] = -1;
  int mx = 0;
  for (int v : G[u]) {
    dfs1(v);
    if (sz[v] > mx) {
      mx = sz[v];
      son[u] = v;
    }
    sz[u] += sz[v];
  }
}
void dfs2(int u, int anc) {
  top[u] = anc;
  if (son[u] != -1) dfs2(son[u], anc);
  for (int v : G[u]) {
    if (v != son[u]) {
      dfs2(v, v);
    }
  }
}
struct node {
  int x, len;
  node(int x, int len) : x(x), len(len) {}
};
vector<node> E[N];
struct query {
  int id, l, r, len;
  query(int id, int l, int r, int len) : id(id), l(l), r(r), len(len) {}
};
vector<query> Q[N];
long long ans[N / 2];
long long sumLen[N], sumX[N], cnt[N];
inline void add(long long *bit, int x, int v) {
  ++x;
  for (; x < N; x += x & -x) {
    bit[x] += v;
  }
}
inline long long read(long long *bit, int x) {
  ++x;
  long long c = 0;
  for (; x; x ^= x & -x) {
    c += bit[x];
  }
  return c;
}
inline void clr(long long *bit, int x) {
  ++x;
  for (; x < N; x += x & -x) {
    bit[x] = 0;
  }
}
void solve(vector<node> &E, vector<query> &Q, int base) {
  sort(E.begin(), E.end(),
       [](const node &a, const node &b) { return a.len < b.len; });
  sort(Q.begin(), Q.end(),
       [](const query &a, const query &b) { return a.len < b.len; });
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumLen, E[j].x + E[j].len + base - 2, E[j].len);
    }
    ans[Q[i].id] += read(sumLen, Q[i].r);
  }
  for (auto &e : E) {
    clr(sumLen, e.x + e.len + base - 2);
  }
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumLen, E[j].x, E[j].len);
    }
    ans[Q[i].id] -= read(sumLen, Q[i].l - 1);
  }
  for (auto &e : E) {
    clr(sumLen, e.x);
  }
  long long totX = 0;
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumX, E[j].x + E[j].len + base - 2, E[j].x + base - 2);
      add(cnt, E[j].x + E[j].len + base - 2, 1);
      totX += E[j].x + base - 2;
    }
    ans[Q[i].id] +=
        (j - read(cnt, Q[i].r)) * Q[i].r - (totX - read(sumX, Q[i].r));
  }
  for (auto &e : E) {
    clr(sumX, e.x + e.len + base - 2);
    clr(cnt, e.x + e.len + base - 2);
  }
  totX = 0;
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumX, E[j].x, E[j].x + base - 2);
      add(cnt, E[j].x, 1);
      totX += E[j].x + base - 2;
    }
    ans[Q[i].id] -= (j - read(cnt, Q[i].r - base + 2)) * Q[i].r -
                    (totX - read(sumX, Q[i].r - base + 2));
  }
  for (auto &e : E) {
    clr(sumX, e.x);
    clr(cnt, e.x);
  }
  for (int i = Q.size() - 1, j = E.size() - 1; i >= 0; --i) {
    for (; j >= 0 && E[j].len > Q[i].len; --j) {
      add(cnt, E[j].x, 1);
      add(sumX, E[j].x, E[j].x + base - 2);
    }
    ans[Q[i].id] += Q[i].len * (read(cnt, Q[i].r - base - Q[i].len + 2) -
                                read(cnt, Q[i].l - 1));
    ans[Q[i].id] += Q[i].r * (read(cnt, Q[i].r - base + 2) -
                              read(cnt, Q[i].r - base - Q[i].len + 2));
    ans[Q[i].id] -= read(sumX, Q[i].r - base + 2) -
                    read(sumX, Q[i].r - base - Q[i].len + 2);
  }
  for (auto &e : E) {
    clr(cnt, e.x);
    clr(sumX, e.x);
  }
}
int main() {
  init();
  scanf("%s", s);
  int n = strlen(s);
  for (int i = n - 1; i >= 0; --i) {
    Extend(s[i] - 'a', i);
  }
  for (int i = 0; i < tot; ++i) {
    if (pool[i].par) {
      G[pool[i].par - pool].push_back(i);
    }
  }
  dfs1(0);
  dfs2(0, 0);
  for (int i = 0; i < n; ++i) {
    int u = leaf[i] - pool;
    while (true) {
      int t = top[u];
      E[t].emplace_back(node(i, pool[u].step - pool[t].minLen() + 1));
      if (!pool[t].par || pool[t].par == pool) {
        break;
      }
      u = pool[t].par - pool;
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l;
    --r;
    int u = leaf[l] - pool;
    while (true) {
      int t = top[u];
      if (pool[t].minLen() <= r - l + 1) {
        Q[t].emplace_back(query(
            i, l, r, min(r - l + 1, pool[u].step) - pool[t].minLen() + 1));
      }
      if (!pool[t].par || pool[t].par == pool) {
        break;
      }
      u = pool[t].par - pool;
    }
  }
  for (int i = 0; i < tot; ++i) {
    if (Q[i].empty()) {
      continue;
    }
    solve(E[i], Q[i], pool[i].minLen());
  }
  for (int i = 0; i < q; ++i) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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 N = 4e5 + 5;
struct Sam {
  Sam *next[26], *par;
  int step, pos;
  int minLen() { return par ? par->step + 1 : 1; }
} pool[N], *root, *last;
int tot;
Sam *newnode(int step) {
  Sam *t = pool + (tot++);
  memset(t->next, 0, sizeof(t->next));
  t->par = NULL;
  t->step = step;
  t->pos = -1;
  return t;
}
void init() {
  tot = 0;
  last = root = newnode(0);
}
Sam *leaf[N / 2];
void Extend(int w, int pos) {
  Sam *p = last;
  Sam *newv = newnode(p->step + 1);
  newv->pos = pos;
  leaf[pos] = newv;
  for (; p && !p->next[w]; p = p->par) p->next[w] = newv;
  if (!p)
    newv->par = root;
  else {
    Sam *q = p->next[w];
    if (q->step == p->step + 1)
      newv->par = q;
    else {
      Sam *nq = newnode(p->step + 1);
      memcpy(nq->next, q->next, sizeof(q->next));
      nq->par = q->par;
      q->par = nq;
      newv->par = nq;
      for (; p && p->next[w] == q; p = p->par) p->next[w] = nq;
    }
  }
  last = newv;
}
char s[N / 2];
vector<int> G[N];
int sz[N], son[N], top[N];
void dfs1(int u) {
  sz[u] = 1;
  son[u] = -1;
  int mx = 0;
  for (int v : G[u]) {
    dfs1(v);
    if (sz[v] > mx) {
      mx = sz[v];
      son[u] = v;
    }
    sz[u] += sz[v];
  }
}
void dfs2(int u, int anc) {
  top[u] = anc;
  if (son[u] != -1) dfs2(son[u], anc);
  for (int v : G[u]) {
    if (v != son[u]) {
      dfs2(v, v);
    }
  }
}
struct node {
  int x, len;
  node(int x, int len) : x(x), len(len) {}
};
vector<node> E[N];
struct query {
  int id, l, r, len;
  query(int id, int l, int r, int len) : id(id), l(l), r(r), len(len) {}
};
vector<query> Q[N];
long long ans[N / 2];
long long sumLen[N], sumX[N], cnt[N];
inline void add(long long *bit, int x, int v) {
  ++x;
  for (; x < N; x += x & -x) {
    bit[x] += v;
  }
}
inline long long read(long long *bit, int x) {
  ++x;
  long long c = 0;
  for (; x; x ^= x & -x) {
    c += bit[x];
  }
  return c;
}
inline void clr(long long *bit, int x) {
  ++x;
  for (; x < N; x += x & -x) {
    bit[x] = 0;
  }
}
void solve(vector<node> &E, vector<query> &Q, int base) {
  sort(E.begin(), E.end(),
       [](const node &a, const node &b) { return a.len < b.len; });
  sort(Q.begin(), Q.end(),
       [](const query &a, const query &b) { return a.len < b.len; });
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumLen, E[j].x + E[j].len + base - 2, E[j].len);
    }
    ans[Q[i].id] += read(sumLen, Q[i].r);
  }
  for (auto &e : E) {
    clr(sumLen, e.x + e.len + base - 2);
  }
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumLen, E[j].x, E[j].len);
    }
    ans[Q[i].id] -= read(sumLen, Q[i].l - 1);
  }
  for (auto &e : E) {
    clr(sumLen, e.x);
  }
  long long totX = 0;
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumX, E[j].x + E[j].len + base - 2, E[j].x + base - 2);
      add(cnt, E[j].x + E[j].len + base - 2, 1);
      totX += E[j].x + base - 2;
    }
    ans[Q[i].id] +=
        (j - read(cnt, Q[i].r)) * Q[i].r - (totX - read(sumX, Q[i].r));
  }
  for (auto &e : E) {
    clr(sumX, e.x + e.len + base - 2);
    clr(cnt, e.x + e.len + base - 2);
  }
  totX = 0;
  for (int j = 0, i = 0; i < Q.size(); ++i) {
    for (; j < E.size() && E[j].len <= Q[i].len; ++j) {
      add(sumX, E[j].x, E[j].x + base - 2);
      add(cnt, E[j].x, 1);
      totX += E[j].x + base - 2;
    }
    ans[Q[i].id] -= (j - read(cnt, Q[i].r - base + 2)) * Q[i].r -
                    (totX - read(sumX, Q[i].r - base + 2));
  }
  for (auto &e : E) {
    clr(sumX, e.x);
    clr(cnt, e.x);
  }
  for (int i = Q.size() - 1, j = E.size() - 1; i >= 0; --i) {
    for (; j >= 0 && E[j].len > Q[i].len; --j) {
      add(cnt, E[j].x, 1);
      add(sumX, E[j].x, E[j].x + base - 2);
    }
    ans[Q[i].id] += Q[i].len * (read(cnt, Q[i].r - base - Q[i].len + 2) -
                                read(cnt, Q[i].l - 1));
    ans[Q[i].id] += Q[i].r * (read(cnt, Q[i].r - base + 2) -
                              read(cnt, Q[i].r - base - Q[i].len + 2));
    ans[Q[i].id] -= read(sumX, Q[i].r - base + 2) -
                    read(sumX, Q[i].r - base - Q[i].len + 2);
  }
  for (auto &e : E) {
    clr(cnt, e.x);
    clr(sumX, e.x);
  }
}
int main() {
  init();
  scanf("%s", s);
  int n = strlen(s);
  for (int i = n - 1; i >= 0; --i) {
    Extend(s[i] - 'a', i);
  }
  for (int i = 0; i < tot; ++i) {
    if (pool[i].par) {
      G[pool[i].par - pool].push_back(i);
    }
  }
  dfs1(0);
  dfs2(0, 0);
  for (int i = 0; i < n; ++i) {
    int u = leaf[i] - pool;
    while (true) {
      int t = top[u];
      E[t].emplace_back(node(i, pool[u].step - pool[t].minLen() + 1));
      if (!pool[t].par || pool[t].par == pool) {
        break;
      }
      u = pool[t].par - pool;
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l;
    --r;
    int u = leaf[l] - pool;
    while (true) {
      int t = top[u];
      if (pool[t].minLen() <= r - l + 1) {
        Q[t].emplace_back(query(
            i, l, r, min(r - l + 1, pool[u].step) - pool[t].minLen() + 1));
      }
      if (!pool[t].par || pool[t].par == pool) {
        break;
      }
      u = pool[t].par - pool;
    }
  }
  for (int i = 0; i < tot; ++i) {
    if (Q[i].empty()) {
      continue;
    }
    solve(E[i], Q[i], pool[i].minLen());
  }
  for (int i = 0; i < q; ++i) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

```