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;
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;
vector<vector<int>> desc;
vector<pair<int, int>> qpaths[MAXQ];
vector<vector<pair<int, int>>> pathqs;
vector<int> qqueries[MAXQ];
const int QCNT = 0, QZSUM = 1, QLENSUM = 2, QCNT2 = 3, QZSUM2 = 4;
struct Q {
  int pathid, kind, lx, hx, hz, mlt;
  long long ans;
  Q(int pathid, int kind, int lx, int hx, int hz, int mlt)
      : pathid(pathid), kind(kind), lx(lx), hx(hx), hz(hz), mlt(mlt), ans(0) {}
};
vector<Q> allqueries;
int addquery(int pathid, int kind, int lx, int hx, int hz, int mlt) {
  int ret = ((int)(allqueries).size());
  allqueries.push_back(Q(pathid, kind, lx, hx, hz, mlt));
  return ret;
}
void query_caplen(int qid, int pathid, int lx, int hx, int val) {
  qqueries[qid].push_back(addquery(pathid, QCNT, lx, hx, val, +val));
  qqueries[qid].push_back(addquery(pathid, QZSUM, lx, hx, val, -1));
  qqueries[qid].push_back(addquery(pathid, QCNT2, lx, hx, val, -val));
  qqueries[qid].push_back(addquery(pathid, QZSUM2, lx, hx, val, +1));
}
void query_capfix(int qid, int pathid, int lx, int hx, int val, int cap) {
  qqueries[qid].push_back(addquery(pathid, QCNT, lx, hx, val, +val));
  qqueries[qid].push_back(addquery(pathid, QZSUM, lx, hx, val, -1));
  qqueries[qid].push_back(
      addquery(pathid, QCNT, lx, hx, val - cap, -(val - cap)));
  qqueries[qid].push_back(addquery(pathid, QZSUM, lx, hx, val - cap, +1));
}
void query_sumlen(int qid, int pathid, int lx, int hx, int hz) {
  qqueries[qid].push_back(addquery(pathid, QLENSUM, lx, hx, hz, -1));
}
void query_sumfix(int qid, int pathid, int lx, int hx, int hz, int val) {
  qqueries[qid].push_back(addquery(pathid, QCNT, lx, hx, hz, -val));
}
void query_special(int qid, int pathid, int lx, int hx, int val, int lz,
                   int hz) {
  qqueries[qid].push_back(addquery(pathid, QCNT, lx, hx, hz, +val));
  qqueries[qid].push_back(addquery(pathid, QZSUM, lx, hx, hz, -1));
  qqueries[qid].push_back(addquery(pathid, QCNT, lx, hx, lz - 1, -val));
  qqueries[qid].push_back(addquery(pathid, QZSUM, lx, hx, lz - 1, +1));
}
vector<long long> bit;
void binit(int n) { bit = vector<long long>(n + 1, 0); }
void bmod(int idx, int by) {
  ++idx;
  while (idx < ((int)(bit).size())) {
    bit[idx] += by;
    idx += idx & -idx;
  }
}
long long bget(int idx) {
  ++idx;
  long long ret = 0;
  while (idx > 0) {
    ret += bit[idx];
    idx -= idx & -idx;
  }
  return ret;
}
void solvequeriesoffline(int pathid) {
  vector<vector<int>> bykind(5);
  for (int i = (0); i < (((int)(allqueries).size())); ++i) {
    assert(allqueries[i].pathid == pathid);
    int kind = allqueries[i].kind;
    bykind[kind].push_back(i);
  }
  for (int kind = (0); kind < (5); ++kind) {
    vector<pair<int, pair<int, int>>> e;
    int pathfst = heavylight.paths[pathid].nodes[0];
    for (int x = (0); x < (((int)(heavylight.paths[pathid].nodes).size()));
         ++x) {
      int at = heavylight.paths[pathid].nodes[x],
          atlen = t.nodes[at].rootlen - t.nodes[pathfst].rootlen +
                  t.nodes[pathfst].parlen;
      for (int i = (0); i < (((int)(desc[at]).size())); ++i) {
        int z = desc[at][i];
        if (kind == QCNT) e.push_back(make_pair(z, make_pair(x, +1)));
        if (kind == QZSUM) e.push_back(make_pair(z, make_pair(x, +z)));
        if (kind == QLENSUM) e.push_back(make_pair(z, make_pair(x, +atlen)));
        if (kind == QCNT2) e.push_back(make_pair(z + atlen, make_pair(x, +1)));
        if (kind == QZSUM2)
          e.push_back(make_pair(z + atlen, make_pair(x, +z + atlen)));
      }
    }
    for (int i = (0); i < (((int)(bykind[kind]).size())); ++i) {
      int qid = bykind[kind][i], hz = allqueries[qid].hz;
      e.push_back(make_pair(hz, make_pair(INT_MAX, qid)));
    }
    sort(e.begin(), e.end());
    binit(((int)(heavylight.paths[pathid].nodes).size()));
    for (int i = (0); i < (((int)(e).size())); ++i) {
      if (e[i].second.first != INT_MAX) {
        bmod(e[i].second.first, e[i].second.second);
      } else {
        int qid = e[i].second.second, lx = allqueries[qid].lx,
            hx = allqueries[qid].hx, mlt = allqueries[qid].mlt;
        long long ans = 0;
        ans += mlt * (bget(hx) - bget(lx - 1));
        allqueries[qid].ans = ans;
      }
    }
  }
}
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);
  desc = vector<vector<int>>(((int)(sufftree.nodes).size()));
  for (int i = (0); i < (slen); ++i) {
    int at = suffixids[slen - i];
    for (int x = at; x != -1;
         x = t.nodes[heavylight.paths[t.nodes[x].pathid].nodes[0]].par)
      desc[x].push_back(i);
  }
  for (int i = (0); i < (nq); ++i)
    qpaths[i] = heavylight.decomposepathtoroot(suffixids[slen - ql[i]]);
  for (int i = (0); i < (nq); ++i) qans[i] = 0;
  pathqs = vector<vector<pair<int, int>>>(((int)(heavylight.paths).size()));
  for (int i = (0); i < (nq); ++i)
    for (int j = (0); j < (((int)(qpaths[i]).size())); ++j) {
      int pathid = qpaths[i][j].first, pathlen = qpaths[i][j].second + 1;
      pathqs[pathid].push_back(make_pair(i, pathlen));
    }
  for (int pathid = (0); pathid < (((int)(heavylight.paths).size()));
       ++pathid) {
    allqueries.clear();
    for (int i = (0); i < (((int)(pathqs[pathid]).size())); ++i) {
      int qid = pathqs[pathid][i].first, pathlen = pathqs[pathid][i].second;
      int lo = -1, hi = pathlen;
      while (lo + 1 < hi) {
        int mi = lo + (hi - lo) / 2;
        int at = heavylight.paths[pathid].nodes[mi];
        if (t.nodes[at].rootlen <= qr[qid] - ql[qid] + 1)
          lo = mi;
        else
          hi = mi;
      }
      int pathfst = heavylight.paths[pathid].nodes[0],
          pathcnt = ((int)(heavylight.paths[pathid].nodes).size()),
          rootparlen = t.nodes[pathfst].rootlen - t.nodes[pathfst].parlen;
      if (lo >= 0) {
        int at = heavylight.paths[pathid].nodes[lo],
            atlen = t.nodes[at].rootlen - rootparlen;
        query_caplen(qid, pathid, 0, lo, qr[qid] + 1 - rootparlen);
        if (lo + 1 < pathcnt)
          query_capfix(qid, pathid, lo + 1, pathcnt - 1,
                       qr[qid] + 1 - rootparlen, atlen);
        if (ql[qid] != 0) {
          query_sumlen(qid, pathid, 0, lo, ql[qid] - 1);
          if (lo + 1 < pathcnt)
            query_sumfix(qid, pathid, lo + 1, pathcnt - 1, ql[qid] - 1, atlen);
        }
      }
      if (lo + 1 < pathlen) {
        int at = heavylight.paths[pathid].nodes[lo + 1],
            atparlen = t.nodes[at].rootlen - t.nodes[at].parlen;
        if (t.nodes[at].par != -1 &&
            t.nodes[t.nodes[at].par].rootlen <= qr[qid] - ql[qid] + 1) {
          query_special(qid, pathid, lo + 1, pathlen - 1,
                        qr[qid] + 1 - atparlen, ql[qid], qr[qid] - atparlen);
        }
      }
    }
    solvequeriesoffline(pathid);
    for (int i = (0); i < (((int)(pathqs[pathid]).size())); ++i) {
      int qid = pathqs[pathid][i].first;
      for (int i = (0); i < (((int)(qqueries[qid]).size())); ++i)
        qans[qid] += allqueries[qqueries[qid][i]].ans;
      qqueries[qid].clear();
    }
  }
}
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(
      (int)std::chrono::steady_clock::now().time_since_epoch().count());
  for (int rep = (0); rep < (1); ++rep) {
    slen = MAXLEN / 10;
    for (int i = (0); i < (slen); ++i) s[i] = 'a' + rng() % 2;
    s[slen] = '\0';
    nq = MAXQ / 10;
    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]);
    }
    solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}