#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++) {
			//
			memset(modulo, 0, 4 * MAXSEQLENGTH * sizeof(int));
			for (int firstIt = 1; firstIt < fragmentLen; firstIt++) {
				modulo[dict[dnaSequence[firstIt - 1] - 'A']][firstIt % divisors[divisorsIt]]++;
			}

			for (int start = fragmentLen; start <= sequenceLength; start++) {
				//
				modulo[dict[dnaSequence[start - 1] - 'A']][start % divisors[divisorsIt]]++;
				if (start >= fragmentLen) {
					if (start > fragmentLen) {
						modulo[dict[dnaSequence[start - fragmentLen - 1] - 'A']][(start - fragmentLen) % 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 - fragmentLen + 1][start] = getMax(preprocMatrix[start - fragmentLen + 1][start], sum);
				}
			}
		}
	}
}

void solveQueries(int preprocMatrix[][MAXSEQLENGTH], int queriesCount) {
	//
	for (int i = 1; i <= queriesCount; i++) {
		//
		int left, right;
		f >> left >> right;
		if (left == right) {
			g << 0 << '\n';
			continue;
		}
		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;
}