// p,i -> p,i+p
#include <fstream>
#include <cstring>
#include <map>
#define DN 605
using namespace std;

int n,m,c[DN][DN],freq[DN][4];
char tx[DN];

int main()
{
    map<char,int> mp;
    mp['A']=0; mp['C']=1; mp['G']=2; mp['T']=3;
    ifstream f("perb.in");
    ofstream g("perb.out");
    f>>n>>m>>tx;
    memset(c,DN,sizeof(c));
    for(int i=0; i<n; ++i) tx[i]=mp[tx[i]];
    for(int i=0; i<n; ++i) for(int p=1; p<=(n-i)/2; ++p) {
        for (int w=0;w<p;++w) for (int q=0;q<4;++q) freq[w][q]=0;
        int k=i;
        for(int q=0; q<p; ++q) ++freq[q][tx[k++]];
        for(int j=2; j<=(n-i)/p; ++j) {
            int bs=0;
            for(int q=0; q<p; ++q) ++freq[q][tx[k++]];
            for(int q=0; q<p; ++q) {
                int nrm=0;
                for(int w=0; w<4; ++w) nrm=max(nrm,freq[q][w]);
                bs+=j-nrm;
            }
            c[i+1][k]=min(c[i+1][k],bs);
        }
    }
    for(int i=1; i<=m; ++i) {
        int a,b;
        f>>a>>b;
        g<<c[a][b]<<'\n';
    }
    return 0;
}