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

const int NMAX = 602;
const int SIGMA = 4;
const int CIFMAX = (1<<14);
int n, m, dp[NMAX*2][NMAX/2+2][SIGMA], minCost[NMAX][NMAX];
char s[NMAX];
char S[CIFMAX];
//ifstream f("perb.in");
ofstream g("perb.out");
int poz;

void next(){
    ++poz; if (poz == CIFMAX){
        fread(S, 1, CIFMAX, stdin); poz = 0;
    }
}

void buf(int &nr){
    nr = 0;
    for(; S[poz]<'0' || S[poz]>'9'; next());
    for(; S[poz]>='0' && S[poz]<='9'; ){
        nr = nr * 10 + (S[poz] - '0');
        next();
    }
}

inline int getCode(const char &cc){
	if (cc == 'A') return 0;
	else if (cc == 'C') return 1;
	else if (cc == 'G') return 2;
	else return 3;
}

inline int max(const int &a,const int &b){
	return (a > b ? a : b );
}
inline int min(const int &a, const int &b){
	return (a < b ? a : b);
}

int main() {
	freopen("perb.in","r", stdin);
	//freopen("perb.out", "w", stdout);
	//cin >> n >> m; cin.get();
	//getline(cin, s);
	//scanf("%d %d\n", &n, &m);
	//scanf("%s", s);
	//f >> n >> m; f.get();
	//getline(f, s);
	scanf("%d %d\n", &n, &m);
	scanf("%s", s);
	for(int i=n; i>=1; --i) s[i] = s[i-1];

	// dp[i][j][0..3] = de cate ori apare 0..3 pe pozitiile i, i+j, i+2*j, ...
	for(int i=n; i>=1; --i){
		for(int j=1; j<=n/2; ++j){
			for(int k=0; k<4; ++k) dp[i][j][k] = dp[i+j][j][k];
			dp[i][j][getCode(s[i])]++;
			//for(int k=0; k<4; ++k) cout << i << " " << j << " " << k << " " << dp[i][j][k] << "\n";
		}
	}
	for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) minCost[i][j] = j-i;
	for(int i=1; i<=n; ++i){
		for(int currPer=1; i+currPer*2-1<=n; currPer++){
			for(int j=i+currPer*2-1; j<=n; j+=currPer){
				int currCost = 0;
				//for(int k=i; k<=i+currPer-1; ++k){
				for(int k=0; k<currPer; ++k){
					int maxTip = 0;
					for(int tip=0; tip<4; ++tip){
						maxTip = max(maxTip, dp[i+k][currPer][tip]-dp[j+k+1][currPer][tip]);
					}
					currCost += (j-i+1) / currPer - maxTip;
					//cout << i << " " << j << " " << currPer << " " << (j-i+1) / currPer - maxTip  << " " << maxTip << " " << (j-i+1)/currPer<< "\n";
				}
				minCost[i][j] = min(minCost[i][j], currCost);
			}
		}
	}

	for(; m; --m){
		int x, y; //scanf("%d %d\n", &x, &y);
		//f >> x >> y;
		buf(x); buf(y);
		//cout << minCost[x][y] << '\n';
		g << minCost[x][y] << "\n";
	}
	return 0;
}