#include <iostream>
using namespace std;

const int NMAX = 601;
const int SIGMA = 4;
int n, m, dp[NMAX][NMAX][SIGMA], minCost[NMAX][NMAX];
string s;

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

int main() {
	freopen("perb.in","r", stdin);
	freopen("perb.out", "w", stdout);
	cin >> n >> m; cin.get();
	getline(cin, s);
	s += "3"; for(int i=(int)s.size()-1; 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; ++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 currPer=1; i+currPer*2-1<=n; currPer++){
			for(int j=i+currPer*2-1; j<=n; j+=currPer){
				minCost[i][j] = j - i; 
				int currCost = 0;
				for(int k=i; k<=i+currPer-1; ++k){
					int maxTip = 0;
					for(int tip=0; tip<4; ++tip){
						maxTip = max(maxTip, dp[k][currPer][tip]-dp[j+k-i+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; cin >> x >> y;
		cout << minCost[x][y] << '\n';
	}
	return 0;
}