# include <fstream>
# include <cstring>
using namespace std ;

# define max(a, b) (a > b ? a : b)
# define min(a, b) (a < b ? a : b)

const char *FIN = "perb.in", *FOU = "perb.out", *adn = { "ACGT" } ;
const int MAX = 605 ;

char S[MAX] ;
int A[MAX][MAX], B[MAX][MAX] ;
int N, M ;

void solve ( int K ) {
    for ( int i = N; i ; --i ) {
        for ( int j = 0, see = i + K > N; j < 4; ++j ) {
            B[i][j] = (S[i] == adn[j]) + (see? 0 : B[i + K][j]) ;
        }
    }

    for ( int i = 1; i <= N; ++i ) {
        for ( int j = i + (K << 1) - 1; j <= N; j += K ) {
            int aux = 0;
            for ( int k = 0; k < K; ++k ) {
                int auxdf = 0, see = j + k + 1 <= N ;
                for ( int l = 0; l < 4; ++l ) {
                    auxdf = max (auxdf, B[i + k][l] - (see ? B[j + k + 1][l] : 0)) ;
                }
                aux += (j - i + 1) / K - auxdf ;
            }
            A[i][j] = min (A[i][j], aux) ;
        }
    }
}

int main (void) {
    ifstream f ( FIN ) ;
    ofstream g ( FOU ) ;

    f >> N >> M >> (S + 1) ;

    memset ( A, 0x3f, sizeof ( A ) ) ;

    for ( int i = 1; i <= N >> 1; ++i ) {
        solve (i) ;
    }

    for ( int i = 1, x, y; i <= M; ++i ) {
        f >> x >> y ;
        g << A[x][y] << '\n' ;
    }
}