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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int STALPH = 26;
struct STNode {
  char *s;
  int len;
  int childs[STALPH];
  int suffix;
  STNode(char *s, int len) : s(s), len(len) {
    memset(childs, -1, sizeof(childs));
    suffix = -1;
  }
};
struct SuffixTree {
  int root;
  vector<STNode> nodes;
  int addnode(char *s, int len) {
    nodes.push_back(STNode(s, len));
    return ((int)(nodes).size()) - 1;
  }
  vector<int> build(char *s) {
    nodes.clear();
    root = addnode(NULL, 0);
    int n = strlen(s), atnode = root, atedge = 0, atlen = 0, pint = -1,
        pleaf = -1;
    for (int i = (0); i <= (n); ++i) {
      while (true) {
        int tonode = atedge == n ? -1 : nodes[atnode].childs[s[atedge] - 'a'];
        if (tonode != -1 && atlen >= nodes[tonode].len) {
          atedge += nodes[tonode].len;
          atlen -= nodes[tonode].len;
          atnode = tonode;
          continue;
        }
        if (tonode == -1) {
          if (i != n) {
            int leaf = addnode(s + i, n - i);
            nodes[atnode].childs[nodes[leaf].s[0] - 'a'] = leaf;
            if (pleaf != -1) nodes[pleaf].suffix = leaf;
            pleaf = leaf;
          } else {
            if (pleaf != -1) nodes[pleaf].suffix = atnode;
            pleaf = -1;
          }
          if (pint != -1) nodes[pint].suffix = atnode;
          pint = -1;
        } else if (i == n || nodes[tonode].s[atlen] != s[i]) {
          int branch = addnode(nodes[tonode].s, atlen);
          nodes[tonode].s += atlen, nodes[tonode].len -= atlen;
          nodes[atnode].childs[nodes[branch].s[0] - 'a'] = branch;
          nodes[branch].childs[nodes[tonode].s[0] - 'a'] = tonode;
          if (i != n) {
            int leaf = addnode(s + i, n - i);
            nodes[branch].childs[nodes[leaf].s[0] - 'a'] = leaf;
            if (pleaf != -1) nodes[pleaf].suffix = leaf;
            pleaf = leaf;
          } else {
            if (pleaf != -1) nodes[pleaf].suffix = branch;
            pleaf = -1;
          }
          if (pint != -1) nodes[pint].suffix = branch;
          pint = branch;
        } else {
          if (pint != -1) assert(atlen == 0), nodes[pint].suffix = atnode;
          pint = -1;
          ++atlen;
          break;
        }
        if (atnode == root) {
          atedge++;
          if (atlen == 0) {
            assert(pint == -1);
            break;
          } else
            --atlen;
        } else {
          atnode = nodes[atnode].suffix;
        }
      }
    }
    vector<int> ret(n + 1, -1);
    for (int at = 1, len = n; at != -1; at = nodes[at].suffix, --len)
      ret[len] = at;
    return ret;
  }
  void print(int at, int depth = 0) {
    for (int i = (0); i < (depth); ++i) printf("  ");
    if (nodes[at].s == NULL)
      printf("<root>");
    else
      printf("'%.*s'", nodes[at].len, nodes[at].s);
    printf(": id=%d", at);
    if (nodes[at].suffix != -1) printf(" suffix=%d", nodes[at].suffix);
    puts("");
    for (int i = (0); i < (STALPH); ++i)
      if (nodes[at].childs[i] != -1) print(nodes[at].childs[i], depth + 1);
  }
};
struct TNode {
  vector<int> ch;
  int parlen;
  int sz, heavy, par, pathid, pathidx, rootlen;
};
struct Tree {
  int root;
  vector<TNode> nodes;
};
struct HLPath {
  vector<int> nodes;
};
struct HeavyLight {
  Tree *t;
  vector<int> prelst;
  vector<HLPath> paths;
  void dfspre(int at) {
    prelst.push_back(at);
    for (int i = (0); i < (((int)(t->nodes[at].ch).size())); ++i)
      dfspre(t->nodes[at].ch[i]);
  }
  void build(Tree *_t) {
    t = _t;
    prelst.clear();
    dfspre(t->root);
    for (int i = ((int)(prelst).size()) - 1; i >= 0; --i) {
      int at = prelst[i];
      t->nodes[at].sz = 1, t->nodes[at].heavy = -1, t->nodes[at].par = -1;
      for (int j = (0); j < (((int)(t->nodes[at].ch).size())); ++j) {
        int to = t->nodes[at].ch[j];
        t->nodes[to].par = at;
        t->nodes[at].sz += t->nodes[to].sz;
        if (t->nodes[at].heavy == -1 ||
            t->nodes[to].sz > t->nodes[t->nodes[at].heavy].sz)
          t->nodes[at].heavy = to;
      }
    }
    paths.clear();
    for (int i = (0); i < (((int)(prelst).size())); ++i) {
      int at = prelst[i];
      t->nodes[at].rootlen =
          t->nodes[at].par == -1
              ? 0
              : t->nodes[t->nodes[at].par].rootlen + t->nodes[at].parlen;
      if (t->nodes[at].par != -1 && t->nodes[t->nodes[at].par].heavy == at)
        continue;
      HLPath path;
      for (int x = at; x != -1; x = t->nodes[x].heavy)
        t->nodes[x].pathid = ((int)(paths).size()),
        t->nodes[x].pathidx = ((int)(path.nodes).size()),
        path.nodes.push_back(x);
      paths.push_back(path);
    }
  }
  vector<pair<int, int>> decomposepathtoroot(int at) {
    vector<pair<int, int>> ret;
    while (at != -1) {
      ret.push_back(make_pair(t->nodes[at].pathid, t->nodes[at].pathidx));
      at = t->nodes[paths[t->nodes[at].pathid].nodes[0]].par;
    }
    reverse(ret.begin(), ret.end());
    return ret;
  }
  void print() {
    for (int i = (0); i < (((int)(paths).size())); ++i) {
      printf("path%d:", i);
      for (int j = (0); j < (((int)(paths[i].nodes).size())); ++j)
        printf(" %d", paths[i].nodes[j]);
      puts("");
    }
  }
};
const int MAXLEN = 200000;
const int MAXQ = 200000;
const int MAXLG = 20;
char s[MAXLEN + 1];
int slen;
int nq;
int ql[MAXQ], qr[MAXQ];
long long qans[MAXQ];
SuffixTree sufftree;
vector<int> suffixids;
Tree t;
HeavyLight heavylight;
struct BIT {
  int n;
  pair<int, long long> all;
  vector<pair<int, long long>> bit;
  BIT() {}
  BIT(int _n) {
    n = _n;
    all = make_pair(0, 0LL);
    bit = vector<pair<int, long long>>(n + 1, make_pair(0, 0LL));
  }
  void mod(int idx, int a, long long b) {
    all.first += a;
    all.second += b;
    ++idx;
    while (idx <= n) {
      bit[idx].first += a;
      bit[idx].second += b;
      idx += idx & -idx;
    }
  }
  pair<int, long long> get(int idx) {
    pair<int, long long> ret = make_pair(0, 0LL);
    ++idx;
    while (idx > 0) {
      ret.first += bit[idx].first;
      ret.second += bit[idx].second;
      idx -= idx & -idx;
    }
    return ret;
  }
  void reset(int _n) {
    n = _n;
    all = make_pair(0, 0LL);
    for (int i = (1); i <= (n); ++i) bit[i] = make_pair(0, 0LL);
  }
};
struct P {
  int id, pathidx, len;
  P(int id, int pathidx, int len) : id(id), pathidx(pathidx), len(len) {}
  P() {}
};
struct Q {
  int id, pathidx, len;
  Q(int id, int pathidx, int len) : id(id), pathidx(pathidx), len(len) {}
  Q() {}
};
struct E {
  int kind, id, pathidx, key, val;
  E(int kind, int id, int pathidx, int key, int val)
      : kind(kind), id(id), pathidx(pathidx), key(key), val(val) {}
  E() {}
};
bool operator<(const E &a, const E &b) {
  if (2 * a.key + a.kind != 2 * b.key + b.kind)
    return 2 * a.key + a.kind < 2 * b.key + b.kind;
  return a.id < b.id;
}
BIT bit(2 * MAXLEN);
vector<vector<P>> plst1;
vector<vector<P>> plst2;
vector<vector<Q>> qlst1;
vector<vector<Q>> qlst2;
vector<vector<Q>> qlst3;
void precalc() {
  auto tstart = std::chrono::system_clock::now();
  plst1 = vector<vector<P>>(((int)(heavylight.paths).size()));
  plst2 = vector<vector<P>>(((int)(heavylight.paths).size()));
  vector<vector<pair<int, P>>> ptmp2(2 * slen);
  for (int id = (0); id < (slen); ++id) {
    int at = suffixids[slen - id];
    while (at != -1) {
      int pathid = t.nodes[at].pathid, pathidx = t.nodes[at].pathidx,
          len = t.nodes[at].rootlen;
      plst1[pathid].push_back(P(id, pathidx, len));
      ptmp2[id + len].push_back(make_pair(pathid, P(id, pathidx, len)));
      at = t.nodes[heavylight.paths[pathid].nodes[0]].par;
    }
  }
  for (int i = (0); i < (((int)(ptmp2).size())); ++i)
    for (int j = (0); j < (((int)(ptmp2[i]).size())); ++j) {
      auto cur = ptmp2[i][j];
      plst2[cur.first].push_back(cur.second);
    }
  fprintf(stderr, "\t%lld\n",
          (long long)((std::chrono::system_clock::now() - tstart).count()));
  qlst1 = vector<vector<Q>>(((int)(heavylight.paths).size()));
  vector<vector<pair<int, Q>>> qtmp1(slen);
  qlst2 = vector<vector<Q>>(((int)(heavylight.paths).size()));
  vector<vector<pair<int, Q>>> qtmp2(slen);
  qlst3 = vector<vector<Q>>(((int)(heavylight.paths).size()));
  vector<vector<pair<int, Q>>> qtmp3(2 * slen);
  for (int id = (0); id < (nq); ++id) {
    int at = suffixids[slen - ql[id]];
    while (at != -1) {
      int pathid = t.nodes[at].pathid, pathidx = t.nodes[at].pathidx,
          len = t.nodes[at].rootlen,
          firstnode = heavylight.paths[pathid].nodes[0],
          h = t.nodes[firstnode].rootlen - t.nodes[firstnode].parlen;
      if (h < qr[id] - ql[id] + 1) {
        {
          int lo = 0, hi = pathidx + 1;
          while (lo + 1 < hi) {
            int mi = lo + (hi - lo) / 2;
            if (t.nodes[heavylight.paths[pathid].nodes[mi - 1]].rootlen >=
                qr[id] - ql[id] + 1)
              hi = mi;
            else
              lo = mi;
          }
          pathidx = lo;
        }
        len = min(t.nodes[heavylight.paths[pathid].nodes[pathidx]].rootlen,
                  qr[id] - ql[id] + 1);
        qtmp1[ql[id]].push_back(make_pair(pathid, Q(id, pathidx, len)));
        qtmp2[qr[id]].push_back(make_pair(pathid, Q(id, pathidx, len)));
        qtmp3[qr[id] - len + slen].push_back(
            make_pair(pathid, Q(id, pathidx, len)));
      }
      at = t.nodes[firstnode].par;
    }
  }
  for (int i = (0); i < (((int)(qtmp1).size())); ++i)
    for (int j = (0); j < (((int)(qtmp1[i]).size())); ++j) {
      auto cur = qtmp1[i][j];
      qlst1[cur.first].push_back(cur.second);
    }
  for (int i = (0); i < (((int)(qtmp2).size())); ++i)
    for (int j = (0); j < (((int)(qtmp2[i]).size())); ++j) {
      auto cur = qtmp2[i][j];
      qlst2[cur.first].push_back(cur.second);
    }
  for (int i = (0); i < (((int)(qtmp3).size())); ++i)
    for (int j = (0); j < (((int)(qtmp3[i]).size())); ++j) {
      auto cur = qtmp3[i][j];
      qlst3[cur.first].push_back(cur.second);
    }
  fprintf(stderr, "\t%lld\n",
          (long long)((std::chrono::system_clock::now() - tstart).count()));
}
void solve() {
  suffixids = sufftree.build(s);
  t.nodes.clear();
  t.root = sufftree.root;
  for (int i = (0); i < (((int)(sufftree.nodes).size())); ++i) {
    TNode tnode;
    tnode.parlen = sufftree.nodes[i].len;
    for (int j = (0); j < (STALPH); ++j)
      if (sufftree.nodes[i].childs[j] != -1)
        tnode.ch.push_back(sufftree.nodes[i].childs[j]);
    t.nodes.push_back(tnode);
  }
  heavylight.build(&t);
  precalc();
  for (int pathid = (0); pathid < (((int)(heavylight.paths).size()));
       ++pathid) {
    int firstnode = heavylight.paths[pathid].nodes[0],
        h = t.nodes[firstnode].rootlen - t.nodes[firstnode].parlen,
        pathlen = ((int)(heavylight.paths[pathid].nodes).size());
    vector<P> &cplst1 = plst1[pathid];
    vector<P> &cplst2 = plst2[pathid];
    vector<Q> &cqlst1 = qlst1[pathid];
    vector<Q> &cqlst2 = qlst2[pathid];
    vector<Q> &cqlst3 = qlst3[pathid];
    {
      int pidx = 0;
      pair<int, long long> all = make_pair(0, 0LL);
      for (int qidx = (0); qidx < (((int)(cqlst2).size())); ++qidx) {
        while (pidx < ((int)(cplst1).size()) &&
               cplst1[pidx].id + h <= qr[cqlst2[qidx].id] + 1)
          all.first += 1, all.second -= cplst1[pidx].id + h, ++pidx;
        qans[cqlst2[qidx].id] +=
            (long long)(qr[cqlst2[qidx].id] + 1) * all.first + all.second;
      }
    }
    {
      int pidx = 0;
      bit.reset(pathlen);
      for (int qidx = (0); qidx < (((int)(cqlst2).size())); ++qidx) {
        while (pidx < ((int)(cplst2).size()) &&
               cplst2[pidx].id + cplst2[pidx].len <= qr[cqlst2[qidx].id] + 1)
          bit.mod(cplst2[pidx].pathidx, +1, cplst2[pidx].id + cplst2[pidx].len),
              ++pidx;
        pair<int, long long> pref = bit.get(cqlst2[qidx].pathidx - 1),
                             all = bit.all;
        qans[cqlst2[qidx].id] +=
            (long long)-(qr[cqlst2[qidx].id] + 1) * pref.first + pref.second;
      }
    }
    {
      int pidx = 0;
      bit.reset(pathlen);
      for (int qidx = (0); qidx < (((int)(cqlst3).size())); ++qidx) {
        while (pidx < ((int)(cplst1).size()) &&
               cplst1[pidx].id <= qr[cqlst3[qidx].id] + 1 - cqlst3[qidx].len)
          bit.mod(cplst1[pidx].pathidx, +1, cplst1[pidx].id), ++pidx;
        pair<int, long long> pref = bit.get(cqlst3[qidx].pathidx - 1),
                             all = bit.all;
        qans[cqlst3[qidx].id] +=
            (long long)-(qr[cqlst3[qidx].id] + 1 - cqlst3[qidx].len) *
                (all.first - pref.first) +
            (all.second - pref.second);
      }
    }
    {
      int pidx = 0;
      bit.reset(pathlen);
      for (int qidx = (0); qidx < (((int)(cqlst1).size())); ++qidx) {
        while (pidx < ((int)(cplst1).size()) &&
               cplst1[pidx].id <= ql[cqlst1[qidx].id] - 1)
          bit.mod(cplst1[pidx].pathidx, +1, cplst1[pidx].len), ++pidx;
        pair<int, long long> pref = bit.get(cqlst1[qidx].pathidx - 1),
                             all = bit.all;
        qans[cqlst1[qidx].id] -= (long long)-(cqlst1[qidx].len) * pref.first +
                                 pref.second +
                                 (long long)(cqlst1[qidx].len - h) * all.first;
      }
    }
  }
}
void run() {
  scanf("%s", s);
  slen = strlen(s);
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d", &ql[i], &qr[i]), --ql[i], --qr[i];
  solve();
  for (int i = (0); i < (nq); ++i) printf("%lld\n", qans[i]);
}
void stress() {
  std::mt19937 rng(231789);
  for (int rep = (0); rep < (10); ++rep) {
    slen = MAXLEN;
    for (int i = (0); i < (slen); ++i) s[i] = 'a' + rng() % 2;
    s[slen] = '\0';
    nq = MAXQ;
    for (int i = (0); i < (nq); ++i) {
      ql[i] = rng() % slen, qr[i] = rng() % slen;
      if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    auto tstart = std::chrono::system_clock::now();
    solve();
    long long chk = 0;
    for (int i = (0); i < (nq); ++i) chk ^= qans[i];
    auto tend = std::chrono::system_clock::now();
    auto duration = (long long)((tend - tstart).count());
    printf("duration: %lld (chk=%lld)\n", duration, chk);
  }
}
int main() {
  run();
  return 0;
}