#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 int take_config(char a)
{
	if (a == 'A') return 0;
	if (a == 'C') return 1;
	if (a == 'G') return 2;
	if (a == 'T') return 3;
}

int main()
{
	fin >> N >> M;
	fin >> S + 1;
	
	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 + (d << 1) <= N; ++i) // first position
		{
			memset(Z, 0, sizeof(Z));
			
			int st = 0;
			for (int j = i; j < i + d; ++j)
			{
				Z[j][0] = Z[j][1] = Z[j][2] = Z[j][3] = 0;
				++Z[++st][take_config(S[j])];
			}
			
			for (int j = i + d; j + d <= N + 1; j += d) // second position
			{
				int nc = 0, start = 0;
				
				for (int k = j; k < j + d; ++k) // update Z[][4] 
				{
					++start;
					++Z[start][take_config(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 (i == 1 && j == 97)
				{
					++i;
					--i;
				}
				
				prec[i][j + d - 1] = min(prec[i][j + d - 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;
}