#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long Inf = 1e18;
const int mod = 0;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename T>
string to_string(T v) {
  int fst = 1;
  string ret = "{";
  for (auto x : v) {
    if (!fst) ret += ",";
    fst = 0, ret += to_string(x);
  }
  ret += "}";
  return ret;
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  dbg_out(T...);
}
const int N = 5e5 + 10;
int fa[N], ch[N][26], len[N], tot = 1, last = 1, pos[N];
void extend(int c) {
  int p = last, np = ++tot;
  last = np;
  len[np] = len[p] + 1;
  for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
  if (!p)
    fa[np] = 1;
  else {
    int q = ch[p][c];
    if (len[p] + 1 == len[q])
      fa[np] = q;
    else {
      int nq = ++tot;
      len[nq] = len[p] + 1;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
  }
}
int n, m;
char s[N];
vector<int> E[N];
const int M = 1e7 + 10;
struct BIT {
  int n = 0, t[N], cur = 0;
  long long c[N];
  void modify(int p, long long v) {
    ++p;
    while (p <= n + 1) {
      if (t[p] != cur) c[p] = 0, t[p] = cur;
      c[p] += v, p += p & -p;
    }
  }
  long long query(int p) {
    if (p < 0) return 0;
    chkmin(p, n);
    ++p;
    long long ret = 0;
    while (p) {
      if (t[p] == cur) ret += c[p];
      p -= p & -p;
    }
    return ret;
  }
  long long querys(int p) {
    if (p >= n) return 0;
    return query(n) - query(p);
  }
  long long querya() { return query(n); }
  void clear() { ++cur; }
} t1, t2;
int son[N], siz[N], dep[N], top[N];
void dfs1(int u) {
  siz[u] = 1, dep[u] = dep[fa[u]] + 1;
  for (auto v : E[u]) {
    dfs1(v), siz[u] += siz[v];
    if (siz[son[u]] < siz[v]) son[u] = v;
  }
}
void dfs2(int u, int tp) {
  top[u] = tp;
  if (son[u]) dfs2(son[u], tp);
  for (auto v : E[u])
    if (v != son[u]) dfs2(v, v);
}
struct option {
  int op, rg, id, to, cmp = 0;
  long long ans = 0;
  bool operator<(const option &A) const {
    return cmp == A.cmp ? op < A.op : cmp < A.cmp;
  }
  option() {}
  option(int _op, int _rg, int _id, int _to = 0) {
    op = _op;
    rg = _rg;
    id = _id;
    to = _to;
  }
};
vector<option> Q[N];
void addm(int i) {
  int u = pos[i];
  while (u) {
    int v = fa[top[u]], w = top[u];
    Q[w].push_back(option(1, len[u] - len[v], i));
    Q[w].push_back(option(2, len[u] - len[v], i));
    u = v;
  }
}
void addq(int l, int r, int id) {
  int u = pos[l];
  while (u) {
    int v = fa[top[u]], w = top[u];
    if (r - l + 1 > len[v]) {
      Q[w].push_back(option(3, min(len[u], r - l + 1) - len[v], l - 1, id));
      Q[w].push_back(option(4, min(len[u], r - l + 1) - len[v], r + 1, id));
    }
    u = v;
  }
}
long long ans[N];
void work(int u) {
  if (Q[u].empty()) return;
  int v = fa[top[u]];
  vector<option> &Q = ::Q[u];
  for (auto &x : Q) {
    if (x.op == 1) x.cmp = x.id;
    if (x.op == 3) x.cmp = x.id;
  }
  sort(Q.begin(), Q.end());
  t1.clear(), t2.clear();
  for (auto &x : Q) {
    if (x.op == 1) {
      t1.modify(x.rg, 1);
      t2.modify(x.rg, x.rg);
    }
    if (x.op == 3) {
      x.ans -= t2.query(x.rg);
      x.ans -= t1.querys(x.rg) * x.rg;
    }
  }
  for (auto &x : Q) {
    if (x.op == 2) x.cmp = x.rg + x.id + len[v] + 1;
    if (x.op == 4) x.cmp = x.id;
  }
  sort(Q.begin(), Q.end());
  t1.clear();
  t2.clear();
  for (auto &x : Q) {
    if (x.op == 2) {
      t1.modify(x.rg, 1);
      t2.modify(x.rg, x.rg);
    }
    if (x.op == 4) {
      x.ans += t2.query(x.rg);
      x.ans += t1.querys(x.rg) * x.rg;
    }
  }
  reverse(Q.begin(), Q.end());
  t1.clear();
  t2.clear();
  for (auto &x : Q) {
    if (x.op == 2) {
      t1.modify(x.id + len[v], 1);
      t2.modify(x.id + len[v], x.id + len[v]);
    }
    if (x.op == 4) {
      x.ans += t1.querys(x.id - x.rg) * x.id;
      x.ans -= t2.querys(x.id - x.rg);
      x.ans += t1.query(x.id - x.rg) * x.rg;
    }
  }
  t1.clear();
  t2.clear();
  for (auto &x : Q) {
    if (x.op == 2) {
      t1.modify(x.id, 1);
      t2.modify(x.id, x.id + len[v]);
    }
    if (x.op == 4) {
      x.ans -= t1.querys(x.id - len[v]) * x.id;
      x.ans += t2.querys(x.id - len[v]);
    }
  }
  for (auto x : Q)
    if (x.op >= 3) ans[x.to] += x.ans;
}
void print() {
  for (int i = 1; i <= tot; i++)
    cerr << "{"
         << "fa[i], len[i]"
         << "}:",
        dbg_out(fa[i], len[i]);
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (int i = n; i; i--) extend(s[i] - 'a'), pos[i] = last;
  for (int i = 2; i <= tot; i++) E[fa[i]].push_back(i);
  dfs1(1), dfs2(1, 1);
  for (int i = 1; i <= n; i++) addm(i);
  m = gi();
  for (int i = 1, l, r; i <= m; i++) l = gi(), r = gi(), addq(l, r, i);
  t1.n = t2.n = N - 2;
  for (int i = 1; i <= tot; i++) work(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 inf = 1e9;
const long long Inf = 1e18;
const int mod = 0;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename T>
string to_string(T v) {
  int fst = 1;
  string ret = "{";
  for (auto x : v) {
    if (!fst) ret += ",";
    fst = 0, ret += to_string(x);
  }
  ret += "}";
  return ret;
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  dbg_out(T...);
}
const int N = 5e5 + 10;
int fa[N], ch[N][26], len[N], tot = 1, last = 1, pos[N];
void extend(int c) {
  int p = last, np = ++tot;
  last = np;
  len[np] = len[p] + 1;
  for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
  if (!p)
    fa[np] = 1;
  else {
    int q = ch[p][c];
    if (len[p] + 1 == len[q])
      fa[np] = q;
    else {
      int nq = ++tot;
      len[nq] = len[p] + 1;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
    }
  }
}
int n, m;
char s[N];
vector<int> E[N];
const int M = 1e7 + 10;
struct BIT {
  int n = 0, t[N], cur = 0;
  long long c[N];
  void modify(int p, long long v) {
    ++p;
    while (p <= n + 1) {
      if (t[p] != cur) c[p] = 0, t[p] = cur;
      c[p] += v, p += p & -p;
    }
  }
  long long query(int p) {
    if (p < 0) return 0;
    chkmin(p, n);
    ++p;
    long long ret = 0;
    while (p) {
      if (t[p] == cur) ret += c[p];
      p -= p & -p;
    }
    return ret;
  }
  long long querys(int p) {
    if (p >= n) return 0;
    return query(n) - query(p);
  }
  long long querya() { return query(n); }
  void clear() { ++cur; }
} t1, t2;
int son[N], siz[N], dep[N], top[N];
void dfs1(int u) {
  siz[u] = 1, dep[u] = dep[fa[u]] + 1;
  for (auto v : E[u]) {
    dfs1(v), siz[u] += siz[v];
    if (siz[son[u]] < siz[v]) son[u] = v;
  }
}
void dfs2(int u, int tp) {
  top[u] = tp;
  if (son[u]) dfs2(son[u], tp);
  for (auto v : E[u])
    if (v != son[u]) dfs2(v, v);
}
struct option {
  int op, rg, id, to, cmp = 0;
  long long ans = 0;
  bool operator<(const option &A) const {
    return cmp == A.cmp ? op < A.op : cmp < A.cmp;
  }
  option() {}
  option(int _op, int _rg, int _id, int _to = 0) {
    op = _op;
    rg = _rg;
    id = _id;
    to = _to;
  }
};
vector<option> Q[N];
void addm(int i) {
  int u = pos[i];
  while (u) {
    int v = fa[top[u]], w = top[u];
    Q[w].push_back(option(1, len[u] - len[v], i));
    Q[w].push_back(option(2, len[u] - len[v], i));
    u = v;
  }
}
void addq(int l, int r, int id) {
  int u = pos[l];
  while (u) {
    int v = fa[top[u]], w = top[u];
    if (r - l + 1 > len[v]) {
      Q[w].push_back(option(3, min(len[u], r - l + 1) - len[v], l - 1, id));
      Q[w].push_back(option(4, min(len[u], r - l + 1) - len[v], r + 1, id));
    }
    u = v;
  }
}
long long ans[N];
void work(int u) {
  if (Q[u].empty()) return;
  int v = fa[top[u]];
  vector<option> &Q = ::Q[u];
  for (auto &x : Q) {
    if (x.op == 1) x.cmp = x.id;
    if (x.op == 3) x.cmp = x.id;
  }
  sort(Q.begin(), Q.end());
  t1.clear(), t2.clear();
  for (auto &x : Q) {
    if (x.op == 1) {
      t1.modify(x.rg, 1);
      t2.modify(x.rg, x.rg);
    }
    if (x.op == 3) {
      x.ans -= t2.query(x.rg);
      x.ans -= t1.querys(x.rg) * x.rg;
    }
  }
  for (auto &x : Q) {
    if (x.op == 2) x.cmp = x.rg + x.id + len[v] + 1;
    if (x.op == 4) x.cmp = x.id;
  }
  sort(Q.begin(), Q.end());
  t1.clear();
  t2.clear();
  for (auto &x : Q) {
    if (x.op == 2) {
      t1.modify(x.rg, 1);
      t2.modify(x.rg, x.rg);
    }
    if (x.op == 4) {
      x.ans += t2.query(x.rg);
      x.ans += t1.querys(x.rg) * x.rg;
    }
  }
  reverse(Q.begin(), Q.end());
  t1.clear();
  t2.clear();
  for (auto &x : Q) {
    if (x.op == 2) {
      t1.modify(x.id + len[v], 1);
      t2.modify(x.id + len[v], x.id + len[v]);
    }
    if (x.op == 4) {
      x.ans += t1.querys(x.id - x.rg) * x.id;
      x.ans -= t2.querys(x.id - x.rg);
      x.ans += t1.query(x.id - x.rg) * x.rg;
    }
  }
  t1.clear();
  t2.clear();
  for (auto &x : Q) {
    if (x.op == 2) {
      t1.modify(x.id, 1);
      t2.modify(x.id, x.id + len[v]);
    }
    if (x.op == 4) {
      x.ans -= t1.querys(x.id - len[v]) * x.id;
      x.ans += t2.querys(x.id - len[v]);
    }
  }
  for (auto x : Q)
    if (x.op >= 3) ans[x.to] += x.ans;
}
void print() {
  for (int i = 1; i <= tot; i++)
    cerr << "{"
         << "fa[i], len[i]"
         << "}:",
        dbg_out(fa[i], len[i]);
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (int i = n; i; i--) extend(s[i] - 'a'), pos[i] = last;
  for (int i = 2; i <= tot; i++) E[fa[i]].push_back(i);
  dfs1(1), dfs2(1, 1);
  for (int i = 1; i <= n; i++) addm(i);
  m = gi();
  for (int i = 1, l, r; i <= m; i++) l = gi(), r = gi(), addq(l, r, i);
  t1.n = t2.n = N - 2;
  for (int i = 1; i <= tot; i++) work(i);
  for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
  return 0;
}

```