#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 num[NMAX][NMAX][4];
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;
	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 + 1;
		}
	}
	
	for (int i = 1; i <= N; ++i)
	{
		for (int j = i; j <= N; ++j)
		{
			num[i][j][0] = num[i][j - 1][0];
			num[i][j][1] = num[i][j - 1][1];
			num[i][j][2] = num[i][j - 1][2];
			num[i][j][3] = num[i][j - 1][3];
			
			++num[i][j][take_config(S[i])];
		}
	}
	
	for (int d = 1; d <= N; ++d) // the divisor
	{
		for (int i = 1; i <= N; ++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][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 (j > i + d) prec[i][j - 1] = min(prec[i][j], nc);
			}
		}
	}
	
	for (int i = 1; i <= M; ++i)
	{
		int X, Y;
		fin >> X >> Y;
		fout << prec[X][Y] << '\n';
	}
	
	fout.close();
	return 0;
}