#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

FILE *f = fopen( "perb.in", "r" );
FILE *g = fopen( "perb.out", "w" );

const int MAXN = 650;
char a[MAXN];
int N, M;
int x, y;
int d[MAXN][MAXN];
int rezj[MAXN][4];
int X[MAXN];
int nr;
int sol;

void Read();
void Dinamica();
void Write();
int Val( char x );

int main()
{
    Read();
    Dinamica();
    Write();
    fclose(f);
    fclose(g);
    return 0;
}

void Read()
{
    int i, j;

    fscanf( f, "%d%d\n", &N, &M );
    fgets( a + 1, MAXN, f );
    for ( i = 1; i <= N; i++ )
        X[i] = Val(a[i]);
}

void Dinamica()
{
    int i, j, k, t;
    for ( i = 1; i <= N; i++ )
        for ( j = i + 1; j <= N; j++ )
            d[i][j] = j - i;

    for ( i = 1; i <= N; i++ )
    {
        for ( j = 1; i + 2*j - 1 <= N; j++ )
        {
        //    if ( i == 5 && j == 3 )
        //        cout << "DA";
            memset( rezj, 0, sizeof(rezj) );
            for ( k = 0; k < j; k++ )
                rezj[k][X[i + k]]++;
            nr = 1;
            sol = 0;
            for ( k = i + j; k + j - 1 <= N; k += j )
            {
                ++nr;
                sol = 0;
                for ( t = 0; t < j; t++ )
                {
                 //   if ( i == 5 && j == 3 && t == 1 )
                //        rezj[1][3]++;
                    rezj[t][X[k + t]]++;
                    sol += (nr - ( max( rezj[t][0], max( rezj[t][1], max( rezj[t][2], rezj[t][3] ) ) ) ));
                }
                d[i][k + j - 1] = min( d[i][j + k - 1], sol );
            }
        }
    }
}

void Write()
{
    int i;
    for ( i = 1; i <= M; i++ )
    {
        fscanf( f, "%d%d", &x, &y );
        fprintf( g, "%d\n", d[x][y] );
    }
}

int Val( char x )
{
    if ( x == 'A' )
        return 0;
    if ( x == 'C' )
        return 1;
    if ( x == 'G' )
        return 2;
    if ( x == 'T' )
        return 3;
    return 10;
}