#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> vc[500005];
vector<pair<int, pair<int, int> > > my[500005], ques2[500005];
vector<pair<pair<int, int>, pair<int, int> > > ques[500005];
int vis[3][500005];
long long ft[3][500005], ans[500005];
int pos[500005], chain[500005], ch, casio;
;
int ou[500005];
char str[500005];
void update2(int id, int p, int v) {
  for (; p <= N; p += p & (-p)) {
    if (vis[id][p] != casio) {
      ft[id][p] = 0;
      vis[id][p] = casio;
    }
    ft[id][p] += v;
  }
}
void update(int a, int b, int v = 1) {
  update2(1, a, v);
  update2(1, b + 1, -v);
  update2(2, a, v * (a - 1));
  update2(2, b + 1, -v * b);
}
long long query2(int id, int b) {
  long long sum = 0;
  for (; b > 0; b -= b & (-b)) {
    if (vis[id][b] != casio) {
      ft[id][b] = 0;
      vis[id][b] = casio;
    }
    sum += ft[id][b];
  }
  return sum;
}
long long query(int b) { return query2(1, b) * b - query2(2, b); }
long long query(int a, int b) {
  if (a > b) return 0;
  return query(b) - query(a - 1);
}
struct state {
  int len, link;
  map<char, int> next;
};
const int MAXLEN = 500500;
state st[MAXLEN];
int sz, last;
void sa_init() {
  sz = last = 0;
  st[0].len = 0;
  st[0].link = -1;
  ++sz;
}
void sa_extend(char c, int id) {
  int cur = sz++;
  pos[id] = cur;
  st[cur].len = st[last].len + 1;
  int p;
  for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
    st[p].next[c] = cur;
  if (p == -1)
    st[cur].link = 0;
  else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len)
      st[cur].link = q;
    else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      for (; p != -1 && st[p].next[c] == q; p = st[p].link)
        st[p].next[c] = clone;
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
int szt[500005];
void dfs(int v) {
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    dfs(w);
    szt[v] += szt[w];
  }
  szt[v]++;
}
int upore[500005];
void heavy(int v) {
  if (chain[ch] == -1) chain[ch] = v;
  upore[v] = chain[ch];
  int ma = -1;
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (ma == -1) {
      ma = w;
    } else if (szt[ma] < szt[w]) {
      ma = w;
    }
  }
  if (ma != -1) heavy(ma);
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (w == ma) continue;
    ch++;
    heavy(w);
  }
}
void prep(int id) {
  sort(my[id].begin(), my[id].end());
  sort(ques[id].begin(), ques[id].end());
  sort(ques2[id].begin(), ques2[id].end());
  int it = 0;
  casio++;
  for (int i = 0; i < ques[id].size(); i++) {
    while (it < my[id].size() && my[id][it].first <= ques[id][i].first.first) {
      int l = my[id][it].first + my[id][it].second.first - 1;
      int r = my[id][it].first + my[id][it].second.second - 1;
      update(l, r);
      it++;
    }
    long long g = query(ques[id][i].second.first, ques[id][i].second.second);
    int no = ques[id][i].first.second;
    if (ou[no])
      ans[no] += g;
    else
      ans[no] -= g;
    ou[no] ^= 1;
  }
  casio++;
  it = 0;
  for (int i = 0; i < ques2[id].size(); i++) {
    while (it < my[id].size() && my[id][it].first <= ques2[id][i].first) {
      int l = my[id][it].second.first;
      int r = my[id][it].second.second;
      update(l, r);
      it++;
    }
    long long g = query(ques2[id][i].second.first);
    int no = ques2[id][i].second.second;
    if (ou[no] == 1)
      ans[no] += g;
    else
      ans[no] -= g;
    ou[no] ^= 1;
  }
}
int len(int v) {
  if (v <= 0) return 0;
  return st[v].len;
}
int main() {
  int i, j, k, l, m;
  memset(chain, -1, sizeof chain);
  scanf("%s", str);
  sa_init();
  int n = strlen(str);
  N = n;
  for (int i = n - 1; i >= 0; i--) {
    sa_extend(str[i], i + 1);
  }
  for (int i = 1; i < sz; i++) {
    vc[st[i].link].push_back(i);
  }
  dfs(0);
  heavy(0);
  for (int i = 1; i <= n; i++) {
    int nd = pos[i];
    while (nd > 0) {
      int v = st[upore[nd]].link;
      int l = len(v) + 1, r = st[nd].len;
      my[upore[nd]].push_back(make_pair(i, make_pair(l, r)));
      nd = v;
    }
  }
  int q;
  cin >> q;
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &l, &k);
    int nd = pos[l];
    while (nd > 0) {
      int v = upore[nd];
      if (len(st[v].link) + 1 <= k - l + 1) {
        int g = min(st[nd].len, k - l + 1);
        ques[v].push_back(make_pair(make_pair(k - g + 1, i), make_pair(l, k)));
        ques[v].push_back(make_pair(make_pair(k, i), make_pair(l, k)));
        ques2[v].push_back(make_pair(l - 1, make_pair(g, i)));
        ques2[v].push_back(make_pair(k - g + 1, make_pair(g, i)));
      }
      nd = st[v].link;
    }
  }
  for (int i = 0; i < sz; i++) prep(i);
  for (int i = 1; i <= q; i++) {
    printf("%lld\n", ans[i]);
  }
}

### 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;
int N;
vector<int> vc[500005];
vector<pair<int, pair<int, int> > > my[500005], ques2[500005];
vector<pair<pair<int, int>, pair<int, int> > > ques[500005];
int vis[3][500005];
long long ft[3][500005], ans[500005];
int pos[500005], chain[500005], ch, casio;
;
int ou[500005];
char str[500005];
void update2(int id, int p, int v) {
  for (; p <= N; p += p & (-p)) {
    if (vis[id][p] != casio) {
      ft[id][p] = 0;
      vis[id][p] = casio;
    }
    ft[id][p] += v;
  }
}
void update(int a, int b, int v = 1) {
  update2(1, a, v);
  update2(1, b + 1, -v);
  update2(2, a, v * (a - 1));
  update2(2, b + 1, -v * b);
}
long long query2(int id, int b) {
  long long sum = 0;
  for (; b > 0; b -= b & (-b)) {
    if (vis[id][b] != casio) {
      ft[id][b] = 0;
      vis[id][b] = casio;
    }
    sum += ft[id][b];
  }
  return sum;
}
long long query(int b) { return query2(1, b) * b - query2(2, b); }
long long query(int a, int b) {
  if (a > b) return 0;
  return query(b) - query(a - 1);
}
struct state {
  int len, link;
  map<char, int> next;
};
const int MAXLEN = 500500;
state st[MAXLEN];
int sz, last;
void sa_init() {
  sz = last = 0;
  st[0].len = 0;
  st[0].link = -1;
  ++sz;
}
void sa_extend(char c, int id) {
  int cur = sz++;
  pos[id] = cur;
  st[cur].len = st[last].len + 1;
  int p;
  for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
    st[p].next[c] = cur;
  if (p == -1)
    st[cur].link = 0;
  else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len)
      st[cur].link = q;
    else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      for (; p != -1 && st[p].next[c] == q; p = st[p].link)
        st[p].next[c] = clone;
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
int szt[500005];
void dfs(int v) {
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    dfs(w);
    szt[v] += szt[w];
  }
  szt[v]++;
}
int upore[500005];
void heavy(int v) {
  if (chain[ch] == -1) chain[ch] = v;
  upore[v] = chain[ch];
  int ma = -1;
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (ma == -1) {
      ma = w;
    } else if (szt[ma] < szt[w]) {
      ma = w;
    }
  }
  if (ma != -1) heavy(ma);
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (w == ma) continue;
    ch++;
    heavy(w);
  }
}
void prep(int id) {
  sort(my[id].begin(), my[id].end());
  sort(ques[id].begin(), ques[id].end());
  sort(ques2[id].begin(), ques2[id].end());
  int it = 0;
  casio++;
  for (int i = 0; i < ques[id].size(); i++) {
    while (it < my[id].size() && my[id][it].first <= ques[id][i].first.first) {
      int l = my[id][it].first + my[id][it].second.first - 1;
      int r = my[id][it].first + my[id][it].second.second - 1;
      update(l, r);
      it++;
    }
    long long g = query(ques[id][i].second.first, ques[id][i].second.second);
    int no = ques[id][i].first.second;
    if (ou[no])
      ans[no] += g;
    else
      ans[no] -= g;
    ou[no] ^= 1;
  }
  casio++;
  it = 0;
  for (int i = 0; i < ques2[id].size(); i++) {
    while (it < my[id].size() && my[id][it].first <= ques2[id][i].first) {
      int l = my[id][it].second.first;
      int r = my[id][it].second.second;
      update(l, r);
      it++;
    }
    long long g = query(ques2[id][i].second.first);
    int no = ques2[id][i].second.second;
    if (ou[no] == 1)
      ans[no] += g;
    else
      ans[no] -= g;
    ou[no] ^= 1;
  }
}
int len(int v) {
  if (v <= 0) return 0;
  return st[v].len;
}
int main() {
  int i, j, k, l, m;
  memset(chain, -1, sizeof chain);
  scanf("%s", str);
  sa_init();
  int n = strlen(str);
  N = n;
  for (int i = n - 1; i >= 0; i--) {
    sa_extend(str[i], i + 1);
  }
  for (int i = 1; i < sz; i++) {
    vc[st[i].link].push_back(i);
  }
  dfs(0);
  heavy(0);
  for (int i = 1; i <= n; i++) {
    int nd = pos[i];
    while (nd > 0) {
      int v = st[upore[nd]].link;
      int l = len(v) + 1, r = st[nd].len;
      my[upore[nd]].push_back(make_pair(i, make_pair(l, r)));
      nd = v;
    }
  }
  int q;
  cin >> q;
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &l, &k);
    int nd = pos[l];
    while (nd > 0) {
      int v = upore[nd];
      if (len(st[v].link) + 1 <= k - l + 1) {
        int g = min(st[nd].len, k - l + 1);
        ques[v].push_back(make_pair(make_pair(k - g + 1, i), make_pair(l, k)));
        ques[v].push_back(make_pair(make_pair(k, i), make_pair(l, k)));
        ques2[v].push_back(make_pair(l - 1, make_pair(g, i)));
        ques2[v].push_back(make_pair(k - g + 1, make_pair(g, i)));
      }
      nd = st[v].link;
    }
  }
  for (int i = 0; i < sz; i++) prep(i);
  for (int i = 1; i <= q; i++) {
    printf("%lld\n", ans[i]);
  }
}

```