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 MOD = 998244353;
namespace IO {
const int BSIZ = 4096;
char bufi[4105], bufo[4105];
int posi = BSIZ, poso;
void getC(char& ch) {
  if (posi == BSIZ) {
    memset(bufi, 0, sizeof(bufi));
    fread(bufi, 1, BSIZ, stdin);
    posi = 0;
  }
  ch = bufi[posi++];
}
template <typename T>
void getU(T& x) {
  char ch;
  x = 0;
  do getC(ch);
  while (ch < '0' || ch > '9');
  do {
    x = x * 10 + (ch - '0');
    getC(ch);
  } while (ch >= '0' && ch <= '9');
}
void getS(char s[], int& len) {
  char ch;
  len = 0;
  do getC(ch);
  while (ch < 'a' || ch > 'z');
  do {
    s[len++] = ch;
    getC(ch);
  } while (ch >= 'a' && ch <= 'z');
}
void putC(char ch) {
  if (ch == EOF || poso == BSIZ) {
    fwrite(bufo, 1, poso, stdout);
    poso = 0;
  }
  if (ch != EOF) bufo[poso++] = ch;
}
char buf[25];
template <typename T>
void putU(T x) {
  int len = 0;
  do {
    buf[len++] = x % 10 + '0';
    x /= 10;
  } while (x != 0);
  for (int i = len - 1; i >= 0; i--) putC(buf[i]);
}
}  // namespace IO
using namespace IO;
int n, q, ql[200005], qr[200005];
char S[200005];
long long ans[200005];
namespace SAM {
int dep[400005], par[400005], nxt[400005][26], cnt;
void init() {
  cnt = 1;
  memset(dep, 0, sizeof(dep));
  memset(par, -1, sizeof(par));
  memset(nxt, -1, sizeof(nxt));
}
int append(int v, int ch) {
  int ret = cnt++;
  dep[ret] = dep[v] + 1;
  for (; v != -1 && nxt[v][ch] == -1; v = par[v]) nxt[v][ch] = ret;
  if (v == -1)
    par[ret] = 0;
  else {
    int ov = nxt[v][ch];
    if (dep[ov] == dep[v] + 1)
      par[ret] = ov;
    else {
      int nv = cnt++;
      dep[nv] = dep[v] + 1;
      par[nv] = par[ov];
      par[ret] = par[ov] = nv;
      for (int i = 0; i < (int)(26); i++) nxt[nv][i] = nxt[ov][i];
      for (; v != -1 && nxt[v][ch] == ov; v = par[v]) nxt[v][ch] = nv;
    }
  }
  return ret;
}
}  // namespace SAM
using namespace SAM;
vector<int> T[400005];
int ver[200005], id[400005];
vector<int> qy[200005];
bool del[400005];
vector<int> hv[400005];
int dfn[400005], dfo[400005], dseq[400005], tot, grp[400005];
void dfs(int v, int par) {
  dfn[v] = tot;
  dseq[tot++] = v;
  for (int i = 0; i < (int)(T[v].size()); i++) {
    int u = T[v][i];
    if (u == par || del[u]) continue;
    dfs(u, v);
  }
  dfo[v] = tot;
}
vector<int> V;
long long psum[200005];
void calc0(int coef, int ld) {
  int len = V.size();
  psum[0] = 0;
  for (int i = 0; i < (int)(len); i++) psum[i + 1] = psum[i] + V[i];
  for (int i = 0; i < (int)(len); i++)
    for (int j = 0; j < (int)(qy[V[i]].size()); j++) {
      int cq = qy[V[i]][j];
      int i0 = max((int)(lower_bound(V.begin(), V.end(), qr[cq] + 1 - ld) -
                         V.begin()),
                   i),
          i1 = lower_bound(V.begin(), V.end(), qr[cq] + 1) - V.begin();
      ans[cq] += coef * (1LL * (i0 - i) * ld + psum[i0] - psum[i] +
                         1LL * (i1 - i0) * (qr[cq] + 1));
    }
}
template <typename T>
struct fwt {
  T sum, dat[400005];
  void add(int id, T val) {
    sum += val;
    for (id++; id < 400005; id += id & -id) dat[id] += val;
  }
  T query(int id) {
    T ret = 0;
    for (id++; id > 0; id -= id & -id) ret += dat[id];
    return ret;
  }
};
fwt<int> tre0;
fwt<long long> tre1;
int qcnt;
pair<int, int> sw[600005];
int gd[400005];
void solve(int r) {
  tot = 0;
  dfs(r, -1);
  int v = r;
  for (int i = 0; i < (int)(tot); i++)
    if ((dfo[dseq[i]] - i) * 2 > tot) v = dseq[i];
  swap(hv[r], hv[v]);
  for (int i = 0; i < (int)(tot); i++) grp[dseq[i]] = r;
  grp[v] = v;
  for (int i = 0; i < (int)(T[v].size()); i++) {
    int u = T[v][i];
    if (dfn[u] < dfn[v] || del[u]) continue;
    for (int j = dfn[u]; j < dfo[u]; j++) grp[dseq[j]] = u;
  }
  for (int i = 0; i < (int)(hv[v].size()); i++)
    if (hv[v][i] != v) hv[grp[hv[v][i]]].push_back(hv[v][i]);
  for (int i = 0; i < (int)(T[v].size()); i++) {
    int u = T[v][i];
    if (dfn[u] < dfn[v] || del[u]) continue;
    V.resize(hv[u].size());
    for (int j = 0; j < (int)(hv[u].size()); j++) V[j] = id[hv[u][j]];
    calc0(-1, dep[v]);
  }
  V.clear();
  V.reserve(hv[v].size() - (v == r ? 0 : hv[r].size()));
  for (int i = 0; i < (int)(hv[v].size()); i++)
    if (r == v || grp[hv[v][i]] != r) V.push_back(id[hv[v][i]]);
  calc0(1, dep[v]);
  if (v != r) {
    for (int i = 0; i < (int)(tot); i++) gd[dseq[i]] = dep[r];
    for (int i = v; i != r; i = par[i]) gd[i] = dep[i];
    for (int i = 0; i < (int)(tot); i++)
      gd[dseq[i]] = max(gd[dseq[i]], gd[par[dseq[i]]]);
    for (int i = 0; i < (int)(hv[r].size()); i++) {
      int u = hv[r][i], cv = id[u];
      for (int j = 0; j < (int)(qy[cv].size()); j++) {
        int cq = qy[cv][j];
        int i0 = lower_bound(V.begin(), V.end(), cv) - V.begin(),
            i1 = max((int)(lower_bound(V.begin(), V.end(), qr[cq] + 1 - gd[u]) -
                           V.begin()),
                     i0),
            i2 = lower_bound(V.begin(), V.end(), qr[cq] + 1) - V.begin();
        ans[cq] += 1LL * (i1 - i0) * gd[u] + psum[i1] - psum[i0] +
                   1LL * (i2 - i1) * (qr[cq] + 1);
      }
    }
    qcnt = 0;
    for (int i = 0; i < (int)(hv[r].size()); i++)
      sw[qcnt++] =
          make_pair(id[hv[r][i]], ~min(id[hv[r][i]] + gd[hv[r][i]], n));
    for (int i = 0; i < (int)(V.size()); i++)
      for (int j = 0; j < (int)(qy[V[i]].size()); j++) {
        int cq = qy[V[i]][j];
        sw[qcnt++] = make_pair(ql[cq] - 1, cq << 1 | 1);
        sw[qcnt++] = make_pair(qr[cq], cq << 1);
      }
    sort(sw, sw + qcnt);
    for (int i = 0; i < (int)(qcnt); i++) {
      int tmp = sw[i].second;
      if (tmp < 0) {
        tmp = ~tmp;
        tre0.add(tmp, 1);
        tre1.add(tmp, tmp);
      } else {
        int coef = tmp & 1 ? -1 : 1;
        tmp >>= 1;
        ans[tmp] +=
            coef * (1LL * (tre0.sum - tre0.query(qr[tmp])) * (qr[tmp] + 1) +
                    tre1.query(qr[tmp]));
      }
    }
    for (int i = 0; i < (int)(qcnt); i++) {
      int tmp = sw[i].second;
      if (tmp < 0) {
        tmp = ~tmp;
        tre0.add(tmp, -1);
        tre1.add(tmp, -tmp);
      }
    }
  }
  del[v] = true;
  if (r != v) solve(r);
  for (int i = 0; i < (int)(T[v].size()); i++) {
    int u = T[v][i];
    if (dfn[u] < dfn[v] || del[u]) continue;
    solve(u);
  }
}
int main() {
  getS(S, n);
  getU(q);
  for (int i = 0; i < (int)(n); i++) S[i] -= 'a';
  for (int i = 0; i < (int)(q); i++) {
    getU(ql[i]);
    getU(qr[i]);
    ql[i]--;
    qr[i]--;
  }
  init();
  for (int i = n - 1; i >= 0; i--) ver[i] = append(ver[i + 1], S[i]);
  for (int i = 0; i < (int)(cnt); i++) id[i] = -1;
  for (int i = 0; i < (int)(n); i++) id[ver[i]] = i;
  for (int i = 1; i <= (int)(cnt - 1); i++) {
    T[par[i]].push_back(i);
    T[i].push_back(par[i]);
  }
  for (int i = 0; i < (int)(q); i++) qy[ql[i]].push_back(i);
  for (int i = 0; i < (int)(n); i++) hv[0].push_back(ver[i]);
  solve(0);
  for (int i = 0; i < (int)(q); i++)
    ans[i] -= 1LL * (ql[i] + qr[i]) * (qr[i] - ql[i] + 1) / 2;
  for (int i = 0; i < (int)(q); i++) {
    putU(ans[i]);
    putC('\n');
  }
  putC(EOF);
  return 0;
}