#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f64 = double_t;
constexpr i64 mod = 998244353;
pair<vector<int>, vector<int>> binary_lifting(const string &s) {
  int n = s.size(), k = 0;
  vector<int> p(n), rank(n), q, count;
  iota(p.begin(), p.end(), 0);
  ranges::sort(p, {}, [&](int i) { return s[i]; });
  for (int i = 0; i < n; i += 1) {
    rank[p[i]] = i and s[p[i]] == s[p[i - 1]] ? rank[p[i - 1]] : k++;
  }
  for (int m = 1; m < n; m *= 2) {
    q.resize(m);
    iota(q.begin(), q.end(), n - m);
    for (int i : p) {
      if (i >= m) { q.push_back(i - m); }
    }
    count.assign(k, 0);
    for (int i : rank) { count[i] += 1; }
    partial_sum(count.begin(), count.end(), count.begin());
    for (int i = n - 1; i >= 0; i -= 1) { p[count[rank[q[i]]] -= 1] = q[i]; }
    auto previous = rank;
    previous.resize(2 * n, -1);
    k = 0;
    for (int i = 0; i < n; i += 1) {
      rank[p[i]] = i and previous[p[i]] == previous[p[i - 1]] and
                           previous[p[i] + m] == previous[p[i - 1] + m]
                       ? rank[p[i - 1]]
                       : k++;
    }
  }
  vector<int> lcp(n);
  k = 0;
  for (int i = 0; i < n; i += 1) {
    if (rank[i]) {
      k = max(k - 1, 0);
      int j = p[rank[i] - 1];
      while (i + k < n and j + k < n and s[i + k] == s[j + k]) { k += 1; }
      lcp[rank[i]] = k;
    }
  }
  return {p, lcp};
}
constexpr int sigma = 26;
struct Node {
  int sum, len, link;
  array<int, sigma> next;
  Node(int len) : len(len) {
    sum = link = 0;
    next.fill(0);
  }
};
struct PalindromicTree : vector<Node> {
  int last;
  vector<int> s;
  PalindromicTree() : last(0) {
    emplace_back(0);
    emplace_back(-1);
    at(0).link = 1;
  }
  int get_link(int u, int i) {
    while (i < at(u).len + 1 or s[i - at(u).len - 1] != s[i]) u = at(u).link;
    return u;
  }
  void extend(int i) {
    int cur = get_link(last, i);
    if (not at(cur).next[s[i]]) {
      int now = size();
      emplace_back(at(cur).len + 2);
      back().link = at(get_link(at(cur).link, i)).next[s[i]];
      back().sum = at(back().link).sum + 1;
      at(cur).next[s[i]] = now;
    }
    last = at(cur).next[s[i]];
  }
};
struct SparseTable {
  vector<vector<int>> table;
  SparseTable() {}
  SparseTable(const vector<int> &a) {
    int n = a.size(), h = bit_width(a.size());
    table.resize(h);
    table[0] = a;
    for (int i = 1; i < h; i += 1) {
      table[i].resize(n - (1 << i) + 1);
      for (int j = 0; j + (1 << i) <= n; j += 1) {
        table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  int query(int l, int r) {
    int h = bit_width(unsigned(r - l)) - 1;
    return min(table[h][l], table[h][r - (1 << h)]);
  }
};
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  string s;
  cin >> n >> s;
  auto rs = s;
  ranges::reverse(rs);
  auto t = "a" + s + rs;
  PalindromicTree pam;
  int m = n * 2;
  pam.s.resize(m + 1);
  vector<int> pid(m + 1);
  for (int i = 0; i <= m; i += 1) {
    pam.s[i] = t[i] - 'a';
    pam.extend(i);
    pid[i] = pam.last;
  }
  auto [sa, lcp] = binary_lifting(t);
  vector<int> rank(m + 1);
  for (int i = 0; i <= m; i += 1) { rank[sa[i]] = i; }
  SparseTable table(lcp);
  int q;
  cin >> q;
  auto get_lcp = [&](int i, int j) {
    if (i == j) { return numeric_limits<int>::max(); }
    i = rank[i];
    j = rank[j];
    if (i > j) { swap(i, j); }
    return table.query(i + 1, j + 1);
  };
  vector<int> l(q), r(q), cp(q), ml(q), mr(q), xlen(q), llen(q), rlen(q);
  vector<vector<pair<int, int>>> query(pam.size());
  for (int i = 0; i < q; i += 1) {
    cin >> l[i] >> r[i];
    int li = l[i], ri = 2 * n + 1 - r[i];
    cp[i] = min(r[i] - l[i] + 1, get_lcp(li, ri));
    if (cp[i] < r[i] - l[i] + 1) {
      ml[i] = l[i] + cp[i];
      mr[i] = r[i] - cp[i];
      xlen[i] = mr[i] - ml[i] + 1;
      query[pid[2 * n + 1 - ml[i]]].emplace_back(i, 0);
      query[pid[mr[i]]].emplace_back(i, 1);
    }
  }
  vector<vector<int>> g(pam.size());
  for (int i = 0; i < ssize(pam); i += 1) {
    if (i != 1) { assert(pam[pam[i].link].len < pam[i].len); }
    if (pam[i].link != 1) { g[pam[i].link].push_back(i); }
  }
  vector<int> stack;
  function<void(int)> dfs = [&](int u) {
    stack.push_back(pam[u].len);
    for (auto [i, lr] : query[u]) {
      if (not lr) {
        llen[i] = *prev(ranges::upper_bound(stack, xlen[i]));
      } else {
        rlen[i] = *prev(ranges::upper_bound(stack, xlen[i]));
      }
    }
    for (int v : g[u]) { dfs(v); }
    stack.pop_back();
  };
  dfs(0);
  for (int i = 0; i < q; i += 1) {
    if (cp[i] == r[i] - l[i] + 1) {
      cout << "0 0\n";
      continue;
    }
    // cerr << cp[i] << " " << llen[i] << " " << rlen[i] << "\n";
    cout << r[i] - l[i] + 1 - (cp[i] * 2 + max(llen[i], rlen[i])) << " ";
    int ans = 0;
    if (llen[i] >= rlen[i]) {
      ans += 1;
      if (cp[i]) { ans += min(get_lcp(ml[i] + llen[i], mr[i] + 1), cp[i]); }
    }
    if (rlen[i] >= llen[i]) {
      ans += 1;
      if (cp[i]) {
        ans +=
            min(get_lcp(2 * n + 1 - (mr[i] - rlen[i]), 2 * n + 1 - (ml[i] - 1)),
                cp[i]);
      }
    }
    cout << ans << "\n";
  }
}