#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <numeric>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2000000000
#define NMAX 605
#define NRCHARS 4

class FileReader
{
private:

	const static int Lmax = 5000;
	int poz;
	char s[Lmax + 1];
	ifstream fin;

	inline void advance()
	{
		++poz;
		if (poz == Lmax)
		{
			fin.read(s, Lmax);
			poz = 0;
		}
	}

public:

	FileReader(const char* file) { fin.open(file); poz = 0; fin.read(s, Lmax); }

	FileReader& operator >>(int& x)
	{
		while (!('0' <= s[poz] && s[poz] <= '9')) advance();
		for (x = 0; '0' <= s[poz] && s[poz] <= '9'; advance())
			x = x * 10 + s[poz] - '0';

		return *this;
	}

	FileReader& getline(char *dest, int nrChars)
	{
		for (int i = 0; i < nrChars && s[poz] != '\n'; ++i, advance())
			dest[i] = s[poz];

		advance();
		return *this;
	}

	FileReader& ignore()
	{
		advance();
		return *this;
	}

	void close()
	{
		fin.close();
	}
};

char s[NMAX];
int nr[NMAX][NRCHARS];
int best[NMAX][NMAX];
int h[256];

void precalc(int);

int main()
{
	int i, n, m;
	FileReader fin("perb.in");
	ofstream fout("perb.out");

	h['A'] = 0;
	h['C'] = 1;
	h['G'] = 2;
	h['T'] = 3;

	(fin >> n >> m).ignore();
	fin.getline(s, NMAX);

	precalc(n);

	for (i = 1; i <= m; ++i)
	{
		int a, b;
		fin >> a >> b; --a; --b;

		fout << best[a][b] << '\n';
	}

	fin.close();
	fout.close();

	return 0;
}

void precalc(int n)
{
	int d, i, lg, j, sum, maxEl, changes;

	for (i = 0; i < n; ++i)
		for (j = i; j < n; ++j)
			best[i][j] = INF;

	for (d = 1; d <= n / 2; ++d)
		for (i = 0; i + 2 * d <= n; ++i)
		{
			memset(nr, 0, sizeof(nr));
			for (j = i; j < i + d; ++j) ++nr[j % d][h[s[j]]];

			for (lg = 2; i + lg * d <= n; ++lg)
			{
				for (j = i + (lg - 1) * d; j < i + lg * d; ++j) ++nr[j % d][h[s[j]]];

				for (changes = 0, j = 0; j < d; ++j)
				{
					sum = accumulate(nr[j], nr[j] + NRCHARS, 0);
					maxEl = *max_element(nr[j], nr[j] + NRCHARS);
					changes += sum - maxEl;
				}

				best[i][i + lg * d - 1] = min(best[i][i + lg * d - 1], changes);
			}
		}
}