#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#pragma GCC optimize("O3")
#pragma GCC target("avx")

using namespace std;

template<typename S,typename T>auto&operator<<(auto&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(auto&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(auto&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(auto&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(auto&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}};
template<typename S,typename T,typename U>
auto& operator<<(auto& o,TRI<S,T,U>& t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll, ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<string> vs;

const int MAX_N = 200005;

class SA_IS
{
private:
    using byte = unsigned char;
    byte mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
    #define tget(i) !!(t[(i)>>3]&mask[(i)&7])
    #define tset(i, b) t[(i)>>3]=(b) ? (mask[(i)&7]|t[(i)>>3]) : ((~mask[(i)&7])&t[(i)>>3])
    #define chr(i) (cs==sizeof(int)?((int*)s)[i]:((byte *)s)[i])
    #define isLMS(i) (i>0 && tget(i) && !tget(i-1))
    void getBuckets(byte *s, int *bkt, int n, int K, int cs, bool end=true){
        fill(bkt, bkt + K + 1, 0);
        for(int i = 0; i < n; i++){
            bkt[chr(i)]++;
        }
        for(int i = 0,tmp = 0; i < K+1; i++){
            tmp += bkt[i];
            bkt[i] = end ? tmp : tmp - bkt[i];
        }
    }
    void induceSAl(byte *t, byte *s, int *bkt, int n, int K, int cs){
        getBuckets(s, bkt, n, K, cs, false);
        for(int i = 0; i < n; i++){
            if(sa[i]>0 && !tget(sa[i]-1)){
                sa[bkt[chr(sa[i]-1)]++] = sa[i]-1;
            }
        }
    }
    void induceSAs(byte *t, byte *s, int *bkt, int n, int K, int cs){
        getBuckets(s, bkt, n, K, cs, true);
        for(int i = n-1; i >= 0; i--){
            if(sa[i] > 0 && tget(sa[i]-1)){
                sa[--bkt[chr(sa[i]-1)]] = sa[i]-1;
            }
        }
    }
    void make_sa(byte *s, int n, int K=128, int cs=1){
        byte t[(n >> 3)+1];
        int bkt[K+1], n1 = 0, name = 0;
        tset(n-2, 0), tset(n-1, 1);
        for(int i = n - 3; i >=0; i--){
            tset(i, (chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1))));
        }
        getBuckets(s, bkt, n, K, cs);
        fill(sa, sa+n, -1);
        for(int i = 1; i < n; i++){
            if(isLMS(i)){
                sa[--bkt[chr(i)]] = i;
            }
        }
        induceSAl(t, s, bkt, n, K, cs);
        induceSAs(t, s, bkt, n, K, cs);
        for(int i = 0; i < n; i++){
            if(isLMS(sa[i])){
                sa[n1++] = sa[i];
            }
        }
        fill(sa + n1, sa + n, -1);
        for(int i = 0, tmp = -1; i < n1; i++){
            int pos = sa[i], diff = false;
            for(int d = 0; d < n && !diff; d++){
                diff = chr(pos+d) != chr(tmp+d) || tget(pos+d) != tget(tmp+d);
                if(!diff && d && (isLMS(pos+d) || isLMS(tmp+d))) break;
            }
            if(diff){
                name++, tmp = pos;
            }
            sa[n1+((pos - (pos & 1)) >> 1)] = name - 1;
        }
        int* s1 = sa + n - n1;
        for(int i = n - 1,j = n - 1; i >= n1; i--){
            if(sa[i] >= 0){
                sa[j--] = sa[i];
            }
        }
        if(name < n1){
            make_sa((byte*)s1, n1, name - 1, sizeof(int));
        }else{
            for(int i = 0; i < n1; i++){
                sa[s1[i]] = i;
            }
        }
        getBuckets(s, bkt, n, K, cs);
        for(int i = 1, j = 0; i < n; i++){
            if(isLMS(i)){
                s1[j++] = i;
            }
        }
        for(int i = 0; i < n1; i++){
            sa[i] = s1[sa[i]];
        }
        fill(sa + n1, sa + n, -1);
        for(int i = n1 - 1; i >= 0; i--){
          int tmp = sa[i];
          sa[i] = -1, sa[--bkt[chr(tmp)]] = tmp;
        }
        induceSAl(t, s, bkt, n, K, cs);
        induceSAs(t, s, bkt, n, K, cs);
    }
    void make_lcp(){
        lcp = new int[sz+1];
        rnk = new int[sz+1];
        for(int i = 0; i <= sz; i++) rnk[sa[i]] = i;
        lcp[0] = 0;
        for(int i = 0, h = 0; i < sz; i++){
            int j = sa[rnk[i]-1];
            if(h > 0) h--;
            for(;j+h<sz&&i+h<sz;h++){
                if(CS[j+h] != CS[i+h]) break;
            }
            lcp[rnk[i]-1] = h;
        }
    }
public:
    bool contain(const string& T){
        int a = 0, b = sz;
        while(b - a > 1){
            int c = (a + b) / 2;
            if(CS.compare(sa[c], T.length(), T) < 0){
                a = c;
            }else{
                b = c;
            }
        }
        return CS.compare(sa[b], T.length(), T) == 0;
    }
    string CS;
    byte* S;
    int sz;
    int *sa, *lcp, *rnk;
    SA_IS(string& arg){
        CS = arg;
        sz = (int)arg.size();
        sa = new int[sz+1];
        S = (byte*)arg.c_str();
        make_sa(S, sz+1);
        make_lcp();
    }
    ~SA_IS(){
        delete[] sa;
        // delete[] lcp; delete[] rnk;
    }
};

#define MAX_BIT 64

struct BitRank {
    // block: bit 列を管理, count: block ごとに立っている 1 の数を管理
    vector<unsigned long long> block;
    vector<int> count;
    BitRank(){}
    void resize(int num) {
        block.resize((num + 1) / MAX_BIT + 1, 0);
        count.resize((int)block.size(), 0);
    }
    // i ビット目を val(0,1) にセット
    inline void set(int i, unsigned long long val) {
        block[i/MAX_BIT] |= (val << (i % MAX_BIT));
    }
    void build() {
        for(int i = 1; i < (int)block.size(); i++){
            count[i] = count[i-1] + __builtin_popcountll(block[i-1]);
        }
    }
    // [0, i) ビットの 1 の数
    inline int rank1(int i) {
        int j = i/MAX_BIT, k = i % MAX_BIT;
        return count[j] + (k ? __builtin_popcountll(block[j] << (MAX_BIT-k)) : 0);
    }
    // [i, j) ビットの 1 の数
    inline int rank1(int i, int j) {
        return rank1(j) - rank1(i);
    }
    // [0, i) ビットの 0 の数
    inline int rank0(int i) {
        return i - rank1(i);
    }
    // [i, j) ビットの 0 の数
    inline int rank0(int i, int j) {
        return rank0(j) - rank0(i);
    }
};

class WaveletMatrix
{
private:
    int height;
    vector<BitRank> B;
    vector<int> pos;
public:
    WaveletMatrix(){}
    WaveletMatrix(vector<int>& vec) :
        WaveletMatrix(vec, *max_element(vec.begin(), vec.end()) + 1) {}
    // sigma:文字の種類数
    WaveletMatrix(vector<int>& vec, int sigma){
        init(vec, sigma);
    }
    void init(vector<int>& vec, int sigma){
        height = (sigma == 1) ? 1 : (MAX_BIT - __builtin_clzll(sigma-1));
        B.resize(height), pos.resize(height);
        for(int i = 0; i < height; i++){
            B[i].resize((int)vec.size());
            for(int j = 0; j < (int)vec.size(); j++) {
                B[i].set(j, get(vec[j], height - i - 1));
            }
            B[i].build();
            auto it = stable_partition(vec.begin(), vec.end(), [&](int c) {
                return !get(c, height - i - 1);
            });
            pos[i] = it - vec.begin();
        }
    }
    // val の i ビット目の値を返す(0,1)
    inline int get(int val, int i) {
        return val >> i & 1;
    }
    // [l, r) の間に現れる値 val の数
    int rank(int val, int l, int r) {
        return rank(val, r) - rank(val, l);
    }
    // [0, i) の間に現れる値 val の数
    int rank(int val, int i) {
        int p = 0;
        for(int j = 0; j < height; j++){
            if(get(val, height - j - 1)){
                p = pos[j] + B[j].rank1(p);
                i = pos[j] + B[j].rank1(i);
            }else{
                p = B[j].rank0(p);
                i = B[j].rank0(i);
            }
        }
        return i - p;
    }
    // [l, r) の k(0,1,2...) 番目に小さい値を返す
    int quantile(int k, int l, int r) {
        int res = 0;
        for(int i = 0; i < height; i++){
            int j = B[i].rank0(l, r);
            if(j > k){
                l = B[i].rank0(l);
                r = B[i].rank0(r);
            }else{
                l = pos[i] + B[i].rank1(l);
                r = pos[i] + B[i].rank1(r);
                k -= j;
                res |= (1 << (height - i - 1));
            }
        }
        return res;
    }
    int rangefreq(int i, int j, int a, int b, int l, int r, int x) {
        if(i == j || r <= a || b <= l) return 0;
        int mid = (l + r) >> 1;
        if(a <= l && r <= b){
            return j - i;
        }else{
            int left = rangefreq(B[x].rank0(i),B[x].rank0(j),a,b,l,mid,x+1);
            int right = rangefreq(pos[x]+B[x].rank1(i),pos[x]+B[x].rank1(j),a,b,mid,r,x+1);
            return left + right;
        }
    }
    // [l,r) で値が [a,b) 内に含まれる数を返す
    int rangefreq(int l, int r, int a, int b) {
        return rangefreq(l, r, a, b, 0, 1 << height, 0);
    }
    int range(int i, int j, int a, int b, int l, int r, int x, int val) {
        if(i == j || r <= a || b <= l) return -1;
        if(r - l == 1) return val;
        int mid = (l + r) >> 1;
        int res = range(B[x].rank0(i),B[x].rank0(j),a,b,l,mid,x+1,val);
        if(res < 0) return range(pos[x]+B[x].rank1(i),pos[x]+B[x].rank1(j),a,b,mid,r,x+1,val+(1 << (height - x - 1)));
        else return res;
    }
    // [l,r) で値が [a,b) 内に最小の数を返す
    int range(int l, int r, int a, int b) {
        return range(l, r, a, b, 0, 1 << height, 0, 0);
    }
};

template<typename T> class SparseTable {
private:
    vector<int> LogTable;
    vector<vector<T> > Table; //最小値を保持
    int sz;
public:
    SparseTable(vector<T>& v){
        sz = (int)v.size();
        LogTable.resize(sz+1);
        for(int i = 2; i < sz + 1; i++){
            LogTable[i] = LogTable[i >> 1] + 1;
        }
        Table.resize(sz,vector<T>(LogTable[sz]+1));
        rep(i,sz){
            Table[i][0] = v[i];
        }
        for(int k = 1; (1 << k) <= sz; k++){
            for(int i = 0; i + (1 << k) <= sz; i++){
                Table[i][k] = min(Table[i][k-1],Table[i + (1 << (k-1))][k-1]);
            }
        }
    }
    T query(int l,int r){
        int k = LogTable[r-l];
        return min(Table[l][k],Table[r-(1<<k)][k]);
    }
};

int unzip[MAX_N];
int l, r, n, q;

bool possible(int cri, SA_IS& sa, WaveletMatrix& wm, SparseTable<int>& st)
{
    int left, right;
    if(unzip[r-cri] == 0 || st.query(unzip[r-cri]-1, unzip[r-cri]) < cri){
        left = unzip[r-cri];
    }else{
        int x = -1, y = unzip[r-cri]-1;
        while(y-x>1){
            int mid = (x+y)/2;
            if(st.query(mid, unzip[r-cri]) >= cri){
                y = mid;
            }else{
                x = mid;
            }
        }
        left = y;
    }
    if(unzip[r-cri] == n-1 || st.query(unzip[r-cri], unzip[r-cri]+1) < cri){
        right = unzip[r-cri];
    }else{
        int x = unzip[r-cri]+1, y = n;
        while(y-x>1){
            int mid = (x+y)/2;
            if(st.query(unzip[r-cri], mid) >= cri){
                x = mid;
            }else{
                y = mid;
            }
        }
        right = x;
    }
    // if(!wm.rangefreq(left, right+1, l+1, r-3*cri-1)) return false;
    int res = wm.range(left, right+1, l+1, r-3*cri-1);
    if(res < 0) return false;
    return wm.rangefreq(left, right+1, res+cri+1, r-2*cri);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> q;
    string s;
    cin >> s;
    SA_IS sa(s);
    vi vec(n), vec2(n-1);
    rep(i,n) vec[i] = sa.sa[i+1], unzip[sa.sa[i+1]] = i;
    rep(i,n-1) vec2[i] = sa.lcp[i+1];
    SparseTable<int> st(vec2);
    WaveletMatrix wm(vec);
    rep(i,q){
        cin >> l >> r;
        --l;
        if(r-l<6){
            cout << "0\n";
            continue;
        }
        int x = 0, y = (r-l-3)/3+1;
        while(y-x>1){
            int mid = (x+y)/2;
            if(possible(mid, sa, wm, st)){
                x = mid;
            }else{
                y = mid;
            }
        }
        cout << x << "\n";
    }
    return 0;
}



Measured memory_bytes: 30424