#include <iostream>
#include <fstream>

using namespace std;

inline short maxim(short a, short b)
{
    return a>b ? a:b;
}

short d[666][33],a[333][666][4],x[666];
char s[666];

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

void solve(short st,short dr)
{
    short l=dr-st+1,minim=l,i,m,j,p;
    for(i=1;i<=d[l][0];++i)
    {
        m=0;
        for(j=0;j<d[l][i];++j)
        {
            p=dr-d[l][i]+j+1;
            a[d[l][i]][st+j][x[st+j]]--;
            m+=maxim(maxim(a[d[l][i]][p][0]-a[d[l][i]][st+j][0],a[d[l][i]][p][1]-a[d[l][i]][st+j][1]),maxim(a[d[l][i]][p][2]-a[d[l][i]][st+j][2],a[d[l][i]][p][3]-a[d[l][i]][st+j][3]));
            a[d[l][i]][st+j][x[st+j]]++;
        }
        if(l-m<minim)
        {
            minim=l-m;
        }
    }
    out<<minim<<"\n";
}




int main()
{
    short n,st,dr,j,k;
    int m,i;
    in>>n>>m;
    in.getline(s+1,1000);
    in.getline(s+1,1000);
    for(i=1;i<=n;++i)
    {
        if(s[i]=='A')
            x[i]=0;
        if(s[i]=='C')
            x[i]=1;
        if(s[i]=='G')
            x[i]=2;
        if(s[i]=='T')
            x[i]=3;
    }
    for(i=1;2*i<=n;++i)
    {
        for(j=1;j<=n;++j)
        {
            if(j>i)
            {
                for(k=0;k<=3;++k)
                {
                    a[i][j][k]=a[i][j-i][k];
                }
            }
            a[i][j][x[j]]++;
        }
    }
    for(i=1;i<=n;++i)
    {
        for(j=1;j<i;++j)
        {
           if(i%j==0)
                d[i][++d[i][0]]=j;
        }
    }
    for(i=1;i<=m;++i)
    {
        in>>st>>dr;
        solve(st,dr);
    }
    return 0;
}