#include <fstream>
using namespace std;

const int N=660,M=2500001,inf=1<<30;
int a[N][N],v[N][N],n,D=-1;
char PRINT[M],s[N];

ifstream in("perb.in");
ofstream out("perb.out");

void add_print(int x)
{
    if (!x)
        return;
    add_print(x/10);
    PRINT[++D]=x%10+'0';
}

int calc(int x,int y,int pas)
{
    int i,j,v[30],rez=0,nr;
    for (i=x;i<x+pas;i++)
    {
        for (j=0;j<27;j++)
            v[j]=0;
        nr=0;
        for (j=i;j<=y;j+=pas)
        {
            v[s[j]-'A']++;
            nr=max(nr,v[s[j]-'A']);
        }
        rez+=(y-x+1)/pas-nr;
    }
    return rez;
}

void desc(int &rez,int x,int y)
{
    int n=y-x+1;
    rez=inf;
    for (int i=2;i*i<=n;i++)
        if (n%i==0)
        {
            while (n%i==0)
                n/=i;
            rez=min(rez,calc(x,y,(y-x+1)/i));
        }
    if (n==y-x+1)
    {
        rez=calc(x,y,1);
        return;
    }
    if (n!=1)
        rez=min(rez,calc(x,y,(y-x+1)/n));
}

void proc()
{
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            desc(a[i][j],i,j);
}

int main()
{
    int m,x,y;
    in>>n>>m>>ws;
    in.getline(s+1,n+1);
    proc();
    while (m--)
    {
        in>>x>>y;
        if (!a[x][y])
            PRINT[++D]='0';
        else
            add_print(a[x][y]);
        PRINT[++D]='\n';
    }
    PRINT[++D]='\0';
    out<<PRINT;
    return 0;
}