#include <algorithm>
#include <iostream>
#include <fstream>
#include <map>

#define MAX 610
#define pb push_back

using namespace std;

map <char, int> norm;
int n, q;
int ap[MAX][4];
short cost[MAX][MAX];
char strCit[2 * MAX];

int main()
{
	ifstream cin("perb.in");
	ofstream cout("perb.out");

	cin >> n >> q;

	cin >> strCit + 1;

	norm['A'] = 0;
	norm['C'] = 1;
	norm['G'] = 2;
	norm['T'] = 3;
	for (int i = 1; i <= n; i++)
		strCit[i] = norm[strCit[i]];

	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			cost[i][j] = n;

	for (int st = 1; st <= n; st++)
		for (int div = 1; div <= (n - st + 1) / 2; div++)
		{
			for (int i = 0; i < div; i++)
				for (int k = 0; k < 4; k++)
					ap[i][k] = 0;

			for (int p = 0; p < div; p++)
				ap[p][strCit[st + p]]++;

			for (int ul = st + div; ul + div <= n + 1; ul += div)
			{
				int c = ul - st + div;
				for (int p = 0; p < div; p++)
				{
					ap[p][strCit[ul + p]]++;

					int sc = 0;
					for (int k = 0; k < 4; k++)
						sc = (sc > ap[p][k])? sc : ap[p][k];

					c -= sc;
				}
				cost[st][ul + div - 1] = (cost[st][ul + div - 1] > c)? c : cost[st][ul + div - 1];
			}
		}

	for (; q; q--)
	{
		int x, y;
		cin >> x >> y;

		cout << cost[x][y] << '\n';
	}

	cin.close();
	cout.close();
	return 0;
}