# include <cstdio>
# include <cstring>

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 ;

# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0

inline int max ( int a, int b ) {
    return (a > b ? a : b) ;
}

inline int min ( int a, int b ) {
    return (a < b ? a : b) ;
}

const int hg = 1 << 13 ;
char ch[hg];
int poz ;

inline void cit ( int &x ) {
    if ( ch[0] == '\0' ) fread ( ch, 1, hg, stdin ) ;
    else for ( ; ch[poz] < '0' || ch[poz] > '9' ; verf ) ;
    for ( x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' ; x = x * 10 + ch[poz] - '0', verf ) ;
}

inline 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 + 2 * K - 1; j <= N; j += K ) {
            int aux = 0;
            for ( int k = 0; k < K; ++k ) {
                int auxdf = 0 ;
                if ( j + k + 1 <= N ) {
                auxdf = B[i + k][0] - B[j + k + 1][0] ;
                auxdf = max (auxdf, B[i + k][1] - B[j + k + 1][1]) ;
                auxdf = max (auxdf, B[i + k][2] - B[j + k + 1][2]) ;
                auxdf = max (auxdf, B[i + k][3] - B[j + k + 1][3]) ;
                } else {
                    auxdf = B[i + k][0] ;
                auxdf = max (auxdf, B[i + k][1]) ;
                auxdf = max (auxdf, B[i + k][2]) ;
                auxdf = max (auxdf, B[i + k][3]) ;
                }
                /*for ( int l = 0, see = j + k + 1 <= N; 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) {
    freopen (FIN, "r", stdin) ;
    freopen (FOU, "w", stdout) ;

    scanf ( "%d %d\n", &N, &M ) ;
    fgets ( S + 1, MAX, stdin ) ;

    for ( int i = 1; i <= N; ++i ) {
        for ( int j = i + 1; j <= N; ++j ) {
            A[i][j] = j - i ;
        }
    }

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

    cit (N) ;
    for ( int i = 1, x, y; i <= M; ++i ) {
        cit (x), cit (y) ;
        printf ( "%d\n", A[x][y] ) ;
    }
}