#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

#define MAXN 612
#define INF (1<<30)
#define ALFA 4
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))

int N, M, cnt[2*MAXN][ALFA], A[MAXN][MAXN];
int S[MAXN];

void baga(int x)
{
	int i, j, k, p;
	memset(cnt, 0, sizeof(cnt));
	for(i = N; i >= 1; i--)
		for(j = 0; j < ALFA; j++)
			cnt[i][j] = cnt[i+x][j] + (S[i] == j);
	for(i = 1; i <= N; i++)
		for(j = i+2*x-1; j <= N; j += x)
		{
			int r = 0;
			for(k = 0; k < x; k++)
			{
				int t = -1;
				for(p = 0; p < ALFA; p++)
					t = max(t, cnt[i+k][p]-cnt[j+k+1][p]);
				r += (j-i+1)/x-t;
			}
			A[i][j] = min(A[i][j], r);
		}
}

int main(void)
{
	int i, j, k;
	freopen("perb.in", "rt", stdin);
	freopen("perb.out", "wt", stdout);

	char sir[1024];
	scanf("%d %d\n", &N, &M);
	scanf("%s\n", &sir);
	for(i = 0; i < N; i++)
	{
		if(sir[i] == 'A') S[i+1] = 0;
		if(sir[i] == 'C') S[i+1] = 1;
		if(sir[i] == 'T') S[i+1] = 2;
		if(sir[i] == 'G') S[i+1] = 3;
	}
	for(i = 1; i <= N; i++)
		for(j = i+1; j <= N; j++)
			A[i][j] = INF;
	for(i = 1; i <= N/2; i++)
		baga(i);
	for(i = 1; i <= M; i++)
	{
		scanf("%d %d\n", &j, &k);
		printf("%d\n", A[j][k]);
	}
	return 0;
}