#include<cstdio>
using namespace std;

#define elem (fn - st + 1)

int v[800], n, m;
int ct[5];

bool is[1000];

int getMiscari(int st, int fn, int pas) {
	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 += elem / pas - _max; 
	}
	return rsp;	
}

int main() {
	int i, j, st, fn, _max, ax, t;
	char c; // optiizare ca sunt numai 4 litere
	
	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 <= m; ++i) {
		scanf("%d%d", &st, &fn);
		for(j = 1; j <= elem / 2; ++j)
			is[j] = 0;
		_max = getMiscari(st, fn, 1);
		for(j = elem / 2; j > 1; --j)
			if(elem % j == 0 && !is[j]) {
				for(t = 2; t <= j / 2; ++t)
					if(t % j == 0)
						is[t] = 1;
				if(	(ax = getMiscari(st, fn, j)) < _max)
					_max = ax;
			}
		printf("%d\n", _max);
	}
	return 0;
}