#include<cstdio>
using namespace std;
#define elem (j - i + 1)

int v[800], n, m;

int getMiscari(int st, int fn, int pas) {
	int ct[5];
	int i, j, _max, rsp = 0;
	for(i = 0; i < pas; ++i) {
		_max = 0;
		for(j = 1; j <= 4; ++j)
			ct[j] = 0;
			
		for(j = st + i; j <= fn; j += pas) 
			++ct[v[j]];
		for(j = 1; j <= 4; ++j)
			if(ct[j] > _max)
				_max = ct[j];
				
		rsp += (fn - st + 1) / pas - _max; 
	}
	return rsp;	
}

int main() {
	int i, j, st, fn, _min, ax, t, k, relem;
	char c; 
	int rsp[602][602];
	
	freopen("perb.in", "rt", stdin);
	freopen("perb.out", "wt", stdout);
	scanf("%d%d", &n, &m);
	scanf("%c", &c);
	for(i = 1; i <= n; ++i) {
		scanf("%c", &c);
		switch(c) {
			case 'A': v[i] = 1; break;
			case 'C': v[i] = 2; break;
			case 'G': v[i] = 3; break;
			case 'T': v[i] = 4; break;
		}
	}
	for(i = 1; i <= n; ++i)
		for(j = i + 1; j <= n; ++j) {
			relem = elem;
			_min = getMiscari(i, j, 1);
			for(k = 2; k * k <= relem; ++k)
				if(relem % k == 0) {
					if( (ax = getMiscari(i, j, elem / k)) < _min )
						_min = ax;
					while(relem % k == 0)
						relem /= k;
				}
			if(relem != 1)
				if( (ax = getMiscari(i, j, elem / relem)) < _min )
					_min = ax;
			rsp[i][j] = _min;
		}
			
	for(i = 1; i <= m; ++i) {
		scanf("%d%d", &st, &fn);
		printf("%d\n", rsp[st][fn]);
	}
	return 0;
}