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

ifstream in("perb.in");
ofstream out("perb.out");

int n,m,r[601][601],cnt[601][4],co,smax;
char s[601];

int main() {
	int i,j,k,d,l,q;
	
	in >> n >> m;
	
	in.getline(s,602);
	in.getline(s,602);
	
	for(i = 0; i!=n; ++i) {
		
		switch(s[i]) {
		case 'A':
			s[i] = 1;
			break;
		case 'C':
			s[i] = 2;
			break;
		case 'T':
			s[i] = 3;
			break;
		case 'G':
			s[i] = 0;			
		}
	}
	
	memset(r, 0x3f, sizeof(r));
	for(i = 1; i<=n; ++i) 
		r[i][i]=0;
	
	for(i = 0; i!=n; ++i)
		for(d = 1; d<=((n-i)>>1); ++d) {
			
			for(j = 0; j!=d; ++j)
				for(k = 0; k!=4; ++k)
					cnt[j][k] = 0;
			
			k = i;
			
			for(j = 0; j!=d; ++j)
				++cnt[j][s[k++]];
			
			for(j = 2; j<=(n - i)/d; ++j) {
				
				for(l = 0; l!=d; ++l)
					++cnt[l][s[k++]];
				
				co = 0;
				
				for(l = 0; l!=d; ++l) {
					smax = 0;
					
					for(q = 0; q!=4; ++q)
						if(cnt[l][q]>smax)
							smax = cnt[l][q];
					
					co += j - smax;
				}
				if(co < r[i+1][k])
					r[i+1][k] = co;
			}
		}
	
	for(i = 0; i!=m; ++i) {
		in >> j >> k;
		
		out << r[j][k] << "\n";
	}
	
	return 0;
}