#include <bits/stdc++.h>
#define MAX 131072
#define MOD 98999
#define INF 2100000000
#define eps 1e-5

using namespace std;
const int NMAX = 610;

int N, M;
int frecv[NMAX][5], dp[NMAX][NMAX];
char s[NMAX];

inline int convToNumber(char ch){
    if(ch == 'A')
        return 0;
    else if(ch == 'C')
        return 1;
    else if(ch == 'G')
        return 2;
    else return 3;
}

int main(){

    freopen("perb.in", "r", stdin);
    freopen("perb.out", "w", stdout);

    scanf("%d%d %s", &N, &M, s + 1);
    for(int i = 1; i <= N; i++)
        for(int j = i + 1; j <= N; j++)
            dp[i][j] = INF;

    for(int period = 1; period <= N / 2; period++){
        for(int i = 1; i <= period; i++){
            for(int j = i; j <= N; j += period){
                for(int ch = 0; ch < 4; ch++)
                    frecv[j][ch] = frecv[max(j - period, 0)][ch];
                frecv[j][convToNumber(s[j])]++;
            }
        }
        for(int i = 1; i <= N; i++){
            for(int j = i + 2 * period - 1; j <= N; j += period){
                int val = 0;
                for(int d = j - period + 1; d <= j; d++){
                    int Max = 0;
                    for(int ch = 0; ch < 4; ch++)
                        Max = max(Max, frecv[d][ch] - frecv[max(0, d + i - j - 1)][ch]);
                    val = val + (j - i + 1) / period - Max;
                }
                dp[i][j] = min(dp[i][j], val);
            }
        }
    }
    int x, y;
    for(int i = 1; i <= M; i++){
        scanf("%d%d", &x, &y);
        printf("%d\n", dp[x][y]);
    }

    return 0;
}