#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 610

using namespace std;

ifstream fin("perb.in");
ofstream fout("perb.out");

int N, M;
char S[NMAX];
int prec[NMAX][NMAX];
int Z[NMAX][4];

inline char take_config(char a)
{
	if (a == 'A') return 0;
	if (a == 'C') return 1;
	if (a == 'G') return 2;
	return 3;
}

int main()
{
	fin >> N >> M;
	fin >> S + 1;
	
	for (int i = 1; i <= N; ++i)
	{
		S[i] = take_config(S[i]);
	}
	
	for (int i = 0; i < NMAX; ++i)
	{
		for (int j = 0; j < NMAX; ++j)
		{
			prec[i][j] = NMAX * 1000;
		}
	}
	
	for (int d = 1; d <= N; ++d) // the divisor
	{
		for (int i = 1; i <= N + 1; ++i) // first position
		{
			memset(Z, 0, sizeof(Z));
			
			for (int j = i + d; j <= N + 1; j += d) // second position
			{
				int nc = 0, start = 0;
				
				for (int k = j - d; k < j; ++k) // update Z[][4] 
				{
					++start;
					++Z[start][S[k]];
					nc = nc + Z[start][0] + Z[start][1] + Z[start][2] + Z[start][3] 
					- max(max(Z[start][0], Z[start][1]), max(Z[start][2], Z[start][3]));
				}
				
				if (j > i + d) prec[i][j - 1] = min(prec[i][j - 1], nc);
			}
		}
	}
	
	for (int i = 1; i <= M; ++i)
	{
		int X, Y;
		fin >> X >> Y;
		if (X > Y) swap(X, Y);
		if (X == Y) fout << "0\n";
		else fout << prec[X][Y] << '\n';
	}
	
	fout.close();
	return 0;
}