#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream si("perb.in");
ofstream so("perb.out");
string v;
int c[605][605];
int ch[605][4];
int maxx[605];
inline int cod(char a)
{
    switch(a)
    {
        case 'A': return 0;
        case 'C': return 1;
        case 'T': return 2;
        case 'G': return 3;
    }
}
int main()
{
    int n,m;
    si>>n>>m;
    si>>v;
    int lg;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            c[i][j]=1000000000;
    for(int d=1;d<=n;++d)
    {

        for(int i=0;i<n;++i)
        {
            lg=0;
            for(int j=0;j<d;++j)
            {
                for(int i=0;i<4;++i)
                {
                    ch[j][i]=0;
                }
                maxx[j]=0;
            }
            for(int j=0;j<d;++j)
            {
                ++lg;
                if(lg==d)
                    lg=0;
                ch[lg][cod(v[i+j])]++;
                maxx[lg]=1;
            }
            int sum=0;
            for(int j=i+d;j<n;++j)
            {
                ++lg;
                if(lg==d)
                    lg=0;
                ++ch[lg][cod(v[j])];
                if(ch[lg][cod(v[j])]>maxx[lg])
                {
                    maxx[lg]++;
                }
                else
                {
                    ++sum;
                }
                if(lg==0)
                {
                    if(sum<c[i][j])
                        c[i][j]=sum;
                }
                //if(d==3&&i==4)
                    //cout<<j<<' '<<'('<<lg<<')'<<' '<<maxx[lg]<<' '<<ch[lg][cod(v[j])]<<' '<<sum<<'\n';
            }
        }
    }
    /*for(int i=0;i<n;++i)
    {
        for(int j=i+1;j<n;++j)
        {
            cout<<i<<' '<<j<<' '<<c[i][j]<<'\n';
        }
        cout<<'\n';
    }*/
    int a,b;
    for(int i=1;i<=m;++i)
    {
        si>>a>>b;
        so<<c[a-1][b-1]<<'\n';
    }
    return 0;
}