#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int nmax = 610;

int N,M,a[nmax],dp[nmax][nmax],nr[nmax][4];
inline int Calc(int k){
 return max(nr[k][0],max(nr[k][1],max(nr[k][2],nr[k][3])));
}
inline void solve(){
 int i,j,k,cnt,q,sol,c;

    memset(dp,INF,sizeof(dp));

 for(i = 1; i <= N/2; ++i)
    for(j = 1; j + i*2 <= N; ++j){
            memset(nr,0,sizeof(nr));
            cnt = c = 0;

        for(k = j;k <= N; k++){
            ++cnt;
                if(cnt > i) cnt-=i;
            ++nr[cnt][a[k]];
                if(cnt == i){
                ++c;
                        sol = 0;
                    for(q = 1; q <= i; ++q)
                        sol = sol + c - Calc(q);

//            if(i == 3 && j == 1 && k == 9)
//                cout << sol <<' ';
                 if(k != i)
                    dp[j][k] = min(dp[j][k],sol);
//                if(i == 1 && j == 1 && k == 3)cout << dp[1][3] <<' ';

                }

        }

     //cout << dp[1][9] <<' '<<i<<'\n';
    }
}
int main(){
    int i,j;
    char ch;
        freopen ("perb.in","r",stdin);
        freopen ("perb.out","w",stdout);
    scanf("%d %d\n",&N,&M);

    for(i = 1; i <= N; ++i){
        scanf("%c",&ch);
            if(ch == 'A')a[i] = 0;
            if(ch == 'C')a[i] = 1;
            if(ch == 'T')a[i] = 2;
            if(ch == 'G')a[i] = 3;
    }
    solve();
    while(M--){
        scanf("%d%d\n",&i,&j);
        printf("%d\n",dp[i][j]);
    }
    return 0;
}