#include <cstdio>
#include <cstring>

const int NMAX = 606;

int N, M, ans[NMAX][NMAX], cnt[NMAX][4];
char s[NMAX];

int main()
{
	freopen("perb.in", "r", stdin);
	scanf("%d %d\n", &N, &M);
	fgets(s, NMAX, stdin);

	for (int i=0;i<N;++i)
		if (s[i]=='A') s[i]=0;
		else
			if (s[i]=='C') s[i]=1;
			else
				if (s[i]=='G') s[i]=2;
				else
					if (s[i]=='T') s[i]=3;
					
	memset(ans, 0x3f, sizeof(ans));
	for (int i=1;i<=N;++i) ans[i][i]=0;

	for (int i=0;i<N;++i)
		for (int d=1;d <= (N-i)/2;++d)
		{
			for (int w=0;w<d;++w)
				for (int q=0;q<4;++q)
					cnt[w][q]=0;
					
			int k=i;
			for (int q=0;q<d;++q)
					++cnt[q][(int)s[k++]];
			for (int j=2;j<=(N - i)/d;++j)
			{
				for (int q=0;q<d;++q)
					++cnt[q][(int)s[k++]];
								
				int ch = 0;
				for (int q=0;q<d;++q)
				{
					int vmax = 0;
					for (int w=0;w<4;++w)
						if (vmax < cnt[q][w]) vmax = cnt[q][w];
					ch += j - vmax;
				}
				if (ans[i+1][k] > ch) ans[i+1][k] = ch;
			}
		}
	
	freopen("perb.out", "w", stdout);
	int x, y;
	while (M--)
	{
		scanf("%d%d", &x, &y);
		printf("%d\n", ans[x][y]);
	}
	
	return 0;
}