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

const int NMAX = 602;
const int SIGMA = 4;
int n, m, dp[NMAX*2][NMAX/2+2][SIGMA], minCost[NMAX][NMAX];
char s[NMAX];

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);
	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);
		cout << minCost[x][y] << '\n';
	}
	return 0;
}