#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int NMAX = 606;

vector<int> Div[606];
int N, M,ans[NMAX][NMAX];
int 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;

	for (int i=1;i<=N;++i) Div[i].pb(1);
	for (int i=2;i<=N;++i)
		if (Div[i].size() == 1)
			for (int j=2*i;j<=N;j+=i)
				Div[j].pb(i);

	for (int i=0;i<N-1;++i)
		for (int len=2;i+len<=N;++len)
		{
			ans[i+1][i+len]=0x3f3f3f3f;
			for (vector<int>::iterator it=Div[len].begin();it!=Div[len].end();++it)
			{
				int per = *it;
				int nr = len/per;
				for (int ii=0;ii<per;++ii)
					for (int jj=0;jj<4;++jj)
						cnt[ii][jj]=0;
				for (int j=0;j<len;++j)
					++cnt[j%per][s[i+j]];

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