#include <fstream>
#include <string.h>
#define MAXQCOUNT 500005
#define MAXSEQLENGTH 605

using namespace std;

ifstream f("perb.in");
ofstream g("perb.out");

struct query {
	int left, right;

	query() {
		left = right = 0;
	}

	query(int l, int r) {
		left = l;
		right = r;
	}
};

void readDNASequence(char *dnaSequence, int &sequenceLength, int &queryCount) {
	//
	f >> sequenceLength >> queryCount;
	f >> dnaSequence;
}

void getDivisors(int number, int *divisors, int &divisorsCount) {
	//
	divisorsCount = 0;

	for (int i = 1; i < number; i++) {
		if (number % i == 0) {
			divisors[++divisorsCount] = i;
		}
	}
}

int getMax(int m1, int m2) {
	//
	return m1 > m2 ? m1 : m2;
}

int divisors[MAXSEQLENGTH], divisorsCount;
int modulo[4][MAXSEQLENGTH], dict[26];

void computePreprocessing(char *dnaSequence, int sequenceLength, int preprocMatrix[][MAXSEQLENGTH]) {
	//

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

	for (int fragmentLen = 1; fragmentLen <= sequenceLength; fragmentLen++) {
		//
		getDivisors(fragmentLen, divisors, divisorsCount);
		
		for (int divisorsIt = 1; divisorsIt <= divisorsCount; divisorsIt++) {
			for (int start = 1; start <= sequenceLength - fragmentLen + 1; start++) {
				//
				memset(modulo, 0, 4 * MAXSEQLENGTH * sizeof(int));

				for (int seqIndex = start; seqIndex < start + fragmentLen; seqIndex++) {
					//
					modulo[dict[dnaSequence[seqIndex - 1] - 'A']][seqIndex % divisors[divisorsIt]]++;
					if (seqIndex - start + 1 >= divisors[divisorsIt]) {
						if (seqIndex - start + 1 > divisors[divisorsIt]) {
							modulo[dict[dnaSequence[seqIndex - start] - 'A']][(seqIndex - start) % divisors[divisorsIt]]--;
						}
						int sum = 0;
						for (int elimin = 0; elimin < divisors[divisorsIt]; elimin++) {
							sum += getMax(modulo[0][elimin], getMax(modulo[1][elimin], getMax(modulo[2][elimin], modulo[3][elimin])));
						}

						preprocMatrix[start][start + fragmentLen - 1] = getMax(preprocMatrix[start][start + fragmentLen - 1], sum);
					}
				}
			}
		}
	}
}

void solveQueries(int preprocMatrix[][MAXSEQLENGTH], int queriesCount) {
	//
	for (int i = 1; i <= queriesCount; i++) {
		//
		int left, right;
		f >> left >> right;

		g << (right - left + 1 - preprocMatrix[left][right]) << '\n';
	}
}

int preprocMatrix[MAXSEQLENGTH][MAXSEQLENGTH];
char dnaSequence[MAXSEQLENGTH];
int sequenceLength, queriesCount;

int main() {
	//

	readDNASequence(dnaSequence, sequenceLength, queriesCount);
	computePreprocessing(dnaSequence, sequenceLength, preprocMatrix);
	solveQueries(preprocMatrix, queriesCount);

	return 0;
}