#include <fstream>
#include <string>

using namespace std;

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

const int nmax= 600;
const int inf= 1<<30;

int sol[nmax+1][nmax+1], f[nmax+1][4];

int nr( char c ) {
    if ( c=='A' ) {
        return 0;
    } else if ( c=='C' ) {
        return 1;
    } else if ( c=='G' ) {
        return 2;
    } else if ( c=='T' ) {
        return 3;
    }
}

int main(  ) {
    int n, m;
    string s;
    fin>>n>>m>>s;

    for ( int i= 1; i<=n; ++i ) {
        for ( int j= i+1; j<=n; ++j ) {
            sol[i][j]= inf;
        }
    }
    for ( int i= 1; i<=n; ++i ) {
        for ( int d= 1, x= 1; d*2<=n-i+1; ++d, x= 1 ) {
            for ( int j= 0; j<=d-1; ++j ) {
                f[j][0]= f[j][1]= f[j][2]= f[j][3]= 0;
                ++f[j][nr(s[i+j-1])];
            }
            for ( int j= 2*d, ans= 0; j<=n-i+1; j+= d, ++x ) {
                for ( int k= 0; k<=d-1; ++k ) {
                    ++f[k][nr(s[i+j+k-d-1])];
                    ans= ans+x+1-max(max(f[k][0], f[k][1]), max(f[k][2], f[k][3]));
                }

                sol[i][i+j-1]= min(sol[i][i+j-1], ans);
                ans= 0;
            }
        }
    }

    for ( int cnt= 1, x, y; cnt<=m; ++cnt ) {
        fin>>x>>y;

        fout<<sol[x][y]<<"\n";
    }

    return 0;
}