#include <bits/stdc++.h>
using namespace std;
struct state {
  int son[26], link, len;
} st[400010];
struct data {
  int x, y, id;
};
char s[400010];
int cnt = 1, last, jump[400010][20], mn_l[400010], mx_l[400010], lg,
    size[400010];
int son[400010], top[400010], now, father[400010], node[400010], n;
int id[400010], pos[400010], tl[400010], tr[400010];
long long res[400010];
vector<int> neigh[400010];
vector<data> Q[400010];
bool cmp1(data a, data b) {
  if (a.y == b.y)
    return a.id < b.id;
  else
    return a.y > b.y;
}
bool cmp2(data a, data b) {
  if (a.x == b.x)
    return a.id < b.id;
  else
    return a.x < b.x;
}
struct ds {
  long long sum[2][400010];
  int m, used[400010], tot, change[400010], P;
  int lowbit(int x) { return x - (x & x - 1); }
  void clear() {
    sum[0][0] = sum[1][0] = 0;
    for (int i = 1; i <= tot; i++)
      sum[0][change[i]] = sum[1][change[i]] = used[change[i]] = 0;
    tot = 0;
  }
  long long query(int c, int x) {
    x += P;
    if (x <= 0) return 0;
    if (x >= m) return sum[c][0];
    long long res = 0;
    while (x) {
      res += sum[c][x];
      x -= lowbit(x);
    }
    return res;
  }
  void modify(int x, int c1, int c0) {
    x += P;
    sum[0][0] += c0;
    sum[1][0] += c1;
    while (x <= m) {
      sum[0][x] += c0;
      sum[1][x] += c1;
      if (used[x] == 0) {
        change[++tot] = x;
        used[x] = 1;
      }
      x += lowbit(x);
    }
  }
} bit;
int get_node(int res, int len) {
  if (len >= mn_l[res]) return res;
  for (int i = lg; i >= 0; i--)
    if (jump[res][i] && mn_l[jump[res][i]] > len) res = jump[res][i];
  return jump[res][0];
}
void insert(int x, int id) {
  int cur = ++cnt, p = last, q;
  st[cur].len = st[last].len + 1;
  last = pos[id] = cur;
  for (; p != -1 && st[p].son[x] == 0; p = st[p].link) st[p].son[x] = cur;
  if (p == -1) {
    st[cur].link = 1;
    return;
  }
  q = st[p].son[x];
  if (st[q].len == st[p].len + 1) {
    st[cur].link = q;
    return;
  }
  int clone = ++cnt;
  st[clone] = st[q];
  st[clone].len = st[p].len + 1;
  st[q].link = st[cur].link = clone;
  for (; p != -1 && st[p].son[x] == q; p = st[p].link) st[p].son[x] = clone;
}
void dfs(int u) {
  size[u] = 1;
  int len = neigh[u].size(), mx = 0;
  for (int i = 0; i <= len - 1; i++) {
    int v = neigh[u][i];
    father[v] = u;
    dfs(v);
    size[u] += size[v];
    if (size[v] > mx) {
      mx = size[v];
      son[u] = v;
    }
  }
}
void connect(int u, int ancient) {
  top[u] = ancient;
  id[u] = ++now;
  node[cnt] = u;
  if (son[u]) connect(son[u], ancient);
  int len = neigh[u].size();
  for (int i = 0; i <= len - 1; i++) {
    int v = neigh[u][i];
    if (v != son[u]) connect(v, v);
  }
}
void solve1(int x) {
  sort(Q[x].begin(), Q[x].end(), cmp1);
  bit.m = n;
  bit.P = 0;
  int len = Q[x].size();
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.x, tmp.x, 1);
    else {
      long long t1 = bit.query(1, tmp.x),
                t0 = bit.sum[0][0] - bit.query(0, tmp.x);
      res[tmp.id] -= t1 + t0 * tmp.x;
    }
  }
  bit.clear();
}
void solve2(int x) {
  int len = Q[x].size();
  sort(Q[x].begin(), Q[x].end(), cmp2);
  bit.m = n + 1;
  bit.P = 1;
  for (int i = len - 1; i >= 0; i--) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y, tmp.y, 1);
    else {
      long long t1 = bit.query(1, tmp.x + tmp.y - 2) - bit.query(1, tmp.y - 3),
                t0;
      t0 = bit.query(0, tmp.x + tmp.y - 2) - bit.query(0, tmp.y - 3);
      res[tmp.id] += t1 + (2 - tmp.y) * t0;
      t0 = bit.sum[0][0] - bit.query(0, tmp.x + tmp.y - 2);
      res[tmp.id] += t0 * tmp.x;
    }
  }
  bit.clear();
  bit.m = 2 * n + 1;
  bit.P = n + 1;
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y - tmp.x, tmp.y, 1);
    else {
      long long t1 = bit.query(1, tmp.y - 2), t0 = bit.query(0, tmp.y - 2);
      res[tmp.id] += t1 + (2 - tmp.y) * t0;
    }
  }
  bit.clear();
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y, tmp.y, 1);
    else {
      long long t1 = bit.query(1, tmp.y - 2), t0 = bit.query(0, tmp.y - 2);
      res[tmp.id] -= t1 + (2 - tmp.y) * t0;
    }
  }
  bit.clear();
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y - tmp.x, tmp.x, 1);
    else {
      long long t1 = bit.sum[1][0] - bit.query(1, tmp.y - 2);
      res[tmp.id] += t1;
    }
  }
  bit.clear();
}
int main() {
  int q;
  scanf("%s", s + 1);
  n = strlen(s + 1);
  reverse(s + 1, s + n + 1);
  last = 1;
  st[1].link = -1;
  for (int i = 1; i <= n; i++) insert(s[i] - 'a', i);
  for (int i = 2; i <= cnt; i++) {
    mx_l[i] = st[i].len;
    mn_l[i] = st[st[i].link].len + 1;
    jump[i][0] = st[i].link;
    neigh[st[i].link].push_back(i);
  }
  int tmp = 1;
  while (tmp <= cnt) {
    tmp *= 2;
    lg++;
  }
  for (int j = 1; j <= lg; j++)
    for (int i = 1; i <= cnt; i++) jump[i][j] = jump[jump[i][j - 1]][j - 1];
  dfs(1);
  connect(1, 1);
  int ch = 0;
  for (int i = 2; i <= cnt; i++)
    if (top[i] == 1 && father[i] == 1) {
      ch = i;
      break;
    }
  for (int i = 2; i <= cnt; i++)
    if (top[i] == 1) top[i] = ch;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int l, r, tmp;
    scanf("%d%d", &l, &r);
    l = n - l + 1;
    r = n - r + 1;
    swap(l, r);
    tmp = get_node(pos[r], r - l + 1);
    while (tmp != 1) {
      int x = top[tmp];
      Q[x].push_back((data){min(r - l + 1, mx_l[tmp]) - mn_l[x] + 1, r + 1, i});
      tmp = father[x];
    }
    tl[i] = l;
    tr[i] = r;
  }
  for (int i = 1; i <= n; i++) {
    int tmp = pos[i];
    while (tmp != 1) {
      int x = top[tmp];
      Q[x].push_back((data){mx_l[tmp] - mn_l[x] + 1, i, -1});
      tmp = father[x];
    }
  }
  for (int i = 2; i <= cnt; i++)
    if (top[i] == i) {
      solve1(i);
      Q[i].clear();
    }
  for (int i = 1; i <= q; i++) {
    int tmp = get_node(pos[tr[i]], tr[i] - tl[i] + 1);
    while (tmp != 1) {
      int x = top[tmp], cur_len = min(tr[i] - tl[i] + 1, mx_l[tmp]);
      Q[x].push_back((data){cur_len - mn_l[x] + 1, tl[i], i});
      tmp = father[x];
    }
  }
  for (int i = 1; i <= n; i++) {
    int tmp = pos[i];
    while (tmp != 1) {
      int x = top[tmp];
      Q[x].push_back((data){mx_l[tmp] - mn_l[x] + 1, i - mn_l[x], -1});
      tmp = father[x];
    }
  }
  for (int i = 2; i <= cnt; i++)
    if (top[i] == i) solve2(i);
  for (int i = 1; i <= q; i++) printf("%lld\n", res[i]);
  return 0;
}

### Prompt

Your task is to create a Cpp solution to 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;
struct state {
  int son[26], link, len;
} st[400010];
struct data {
  int x, y, id;
};
char s[400010];
int cnt = 1, last, jump[400010][20], mn_l[400010], mx_l[400010], lg,
    size[400010];
int son[400010], top[400010], now, father[400010], node[400010], n;
int id[400010], pos[400010], tl[400010], tr[400010];
long long res[400010];
vector<int> neigh[400010];
vector<data> Q[400010];
bool cmp1(data a, data b) {
  if (a.y == b.y)
    return a.id < b.id;
  else
    return a.y > b.y;
}
bool cmp2(data a, data b) {
  if (a.x == b.x)
    return a.id < b.id;
  else
    return a.x < b.x;
}
struct ds {
  long long sum[2][400010];
  int m, used[400010], tot, change[400010], P;
  int lowbit(int x) { return x - (x & x - 1); }
  void clear() {
    sum[0][0] = sum[1][0] = 0;
    for (int i = 1; i <= tot; i++)
      sum[0][change[i]] = sum[1][change[i]] = used[change[i]] = 0;
    tot = 0;
  }
  long long query(int c, int x) {
    x += P;
    if (x <= 0) return 0;
    if (x >= m) return sum[c][0];
    long long res = 0;
    while (x) {
      res += sum[c][x];
      x -= lowbit(x);
    }
    return res;
  }
  void modify(int x, int c1, int c0) {
    x += P;
    sum[0][0] += c0;
    sum[1][0] += c1;
    while (x <= m) {
      sum[0][x] += c0;
      sum[1][x] += c1;
      if (used[x] == 0) {
        change[++tot] = x;
        used[x] = 1;
      }
      x += lowbit(x);
    }
  }
} bit;
int get_node(int res, int len) {
  if (len >= mn_l[res]) return res;
  for (int i = lg; i >= 0; i--)
    if (jump[res][i] && mn_l[jump[res][i]] > len) res = jump[res][i];
  return jump[res][0];
}
void insert(int x, int id) {
  int cur = ++cnt, p = last, q;
  st[cur].len = st[last].len + 1;
  last = pos[id] = cur;
  for (; p != -1 && st[p].son[x] == 0; p = st[p].link) st[p].son[x] = cur;
  if (p == -1) {
    st[cur].link = 1;
    return;
  }
  q = st[p].son[x];
  if (st[q].len == st[p].len + 1) {
    st[cur].link = q;
    return;
  }
  int clone = ++cnt;
  st[clone] = st[q];
  st[clone].len = st[p].len + 1;
  st[q].link = st[cur].link = clone;
  for (; p != -1 && st[p].son[x] == q; p = st[p].link) st[p].son[x] = clone;
}
void dfs(int u) {
  size[u] = 1;
  int len = neigh[u].size(), mx = 0;
  for (int i = 0; i <= len - 1; i++) {
    int v = neigh[u][i];
    father[v] = u;
    dfs(v);
    size[u] += size[v];
    if (size[v] > mx) {
      mx = size[v];
      son[u] = v;
    }
  }
}
void connect(int u, int ancient) {
  top[u] = ancient;
  id[u] = ++now;
  node[cnt] = u;
  if (son[u]) connect(son[u], ancient);
  int len = neigh[u].size();
  for (int i = 0; i <= len - 1; i++) {
    int v = neigh[u][i];
    if (v != son[u]) connect(v, v);
  }
}
void solve1(int x) {
  sort(Q[x].begin(), Q[x].end(), cmp1);
  bit.m = n;
  bit.P = 0;
  int len = Q[x].size();
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.x, tmp.x, 1);
    else {
      long long t1 = bit.query(1, tmp.x),
                t0 = bit.sum[0][0] - bit.query(0, tmp.x);
      res[tmp.id] -= t1 + t0 * tmp.x;
    }
  }
  bit.clear();
}
void solve2(int x) {
  int len = Q[x].size();
  sort(Q[x].begin(), Q[x].end(), cmp2);
  bit.m = n + 1;
  bit.P = 1;
  for (int i = len - 1; i >= 0; i--) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y, tmp.y, 1);
    else {
      long long t1 = bit.query(1, tmp.x + tmp.y - 2) - bit.query(1, tmp.y - 3),
                t0;
      t0 = bit.query(0, tmp.x + tmp.y - 2) - bit.query(0, tmp.y - 3);
      res[tmp.id] += t1 + (2 - tmp.y) * t0;
      t0 = bit.sum[0][0] - bit.query(0, tmp.x + tmp.y - 2);
      res[tmp.id] += t0 * tmp.x;
    }
  }
  bit.clear();
  bit.m = 2 * n + 1;
  bit.P = n + 1;
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y - tmp.x, tmp.y, 1);
    else {
      long long t1 = bit.query(1, tmp.y - 2), t0 = bit.query(0, tmp.y - 2);
      res[tmp.id] += t1 + (2 - tmp.y) * t0;
    }
  }
  bit.clear();
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y, tmp.y, 1);
    else {
      long long t1 = bit.query(1, tmp.y - 2), t0 = bit.query(0, tmp.y - 2);
      res[tmp.id] -= t1 + (2 - tmp.y) * t0;
    }
  }
  bit.clear();
  for (int i = 0; i <= len - 1; i++) {
    data tmp = Q[x][i];
    if (tmp.id == -1)
      bit.modify(tmp.y - tmp.x, tmp.x, 1);
    else {
      long long t1 = bit.sum[1][0] - bit.query(1, tmp.y - 2);
      res[tmp.id] += t1;
    }
  }
  bit.clear();
}
int main() {
  int q;
  scanf("%s", s + 1);
  n = strlen(s + 1);
  reverse(s + 1, s + n + 1);
  last = 1;
  st[1].link = -1;
  for (int i = 1; i <= n; i++) insert(s[i] - 'a', i);
  for (int i = 2; i <= cnt; i++) {
    mx_l[i] = st[i].len;
    mn_l[i] = st[st[i].link].len + 1;
    jump[i][0] = st[i].link;
    neigh[st[i].link].push_back(i);
  }
  int tmp = 1;
  while (tmp <= cnt) {
    tmp *= 2;
    lg++;
  }
  for (int j = 1; j <= lg; j++)
    for (int i = 1; i <= cnt; i++) jump[i][j] = jump[jump[i][j - 1]][j - 1];
  dfs(1);
  connect(1, 1);
  int ch = 0;
  for (int i = 2; i <= cnt; i++)
    if (top[i] == 1 && father[i] == 1) {
      ch = i;
      break;
    }
  for (int i = 2; i <= cnt; i++)
    if (top[i] == 1) top[i] = ch;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int l, r, tmp;
    scanf("%d%d", &l, &r);
    l = n - l + 1;
    r = n - r + 1;
    swap(l, r);
    tmp = get_node(pos[r], r - l + 1);
    while (tmp != 1) {
      int x = top[tmp];
      Q[x].push_back((data){min(r - l + 1, mx_l[tmp]) - mn_l[x] + 1, r + 1, i});
      tmp = father[x];
    }
    tl[i] = l;
    tr[i] = r;
  }
  for (int i = 1; i <= n; i++) {
    int tmp = pos[i];
    while (tmp != 1) {
      int x = top[tmp];
      Q[x].push_back((data){mx_l[tmp] - mn_l[x] + 1, i, -1});
      tmp = father[x];
    }
  }
  for (int i = 2; i <= cnt; i++)
    if (top[i] == i) {
      solve1(i);
      Q[i].clear();
    }
  for (int i = 1; i <= q; i++) {
    int tmp = get_node(pos[tr[i]], tr[i] - tl[i] + 1);
    while (tmp != 1) {
      int x = top[tmp], cur_len = min(tr[i] - tl[i] + 1, mx_l[tmp]);
      Q[x].push_back((data){cur_len - mn_l[x] + 1, tl[i], i});
      tmp = father[x];
    }
  }
  for (int i = 1; i <= n; i++) {
    int tmp = pos[i];
    while (tmp != 1) {
      int x = top[tmp];
      Q[x].push_back((data){mx_l[tmp] - mn_l[x] + 1, i - mn_l[x], -1});
      tmp = father[x];
    }
  }
  for (int i = 2; i <= cnt; i++)
    if (top[i] == i) solve2(i);
  for (int i = 1; i <= q; i++) printf("%lld\n", res[i]);
  return 0;
}

```