#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];
int tree[4 * MAXSEQLENGTH];

void updateTree(int *tree, int node, int left, int right, int position, int value) {
	//
	if (left == right && left == position) {
		tree[node] = value; 
		return;
	}

	int middle = (left + right) / 2;
	
	if (position <= middle) {
		updateTree(tree, 2 * node, left, middle, position, value);
	}

	if (position > middle) {
		updateTree(tree, 2 * node + 1, middle + 1, right, position, value);
	}

	tree[node] = tree[2 * node] + tree[2 * node + 1];
}

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));
			memset(tree, 0, 4 * MAXSEQLENGTH * sizeof(int));

			for (int fragmentIt = 1; fragmentIt < fragmentLen; fragmentIt++) {
				//
				int positionInMatrix = fragmentIt % divisors[divisorsIt];
				modulo[dict[dnaSequence[fragmentIt - 1] - 'A']][positionInMatrix]++;
				
				int maxForPosition = getMax(modulo[0][positionInMatrix], getMax(modulo[1][positionInMatrix], getMax(modulo[2][positionInMatrix], modulo[3][positionInMatrix])));
				updateTree(tree, 1, 0, divisors[divisorsIt] - 1, positionInMatrix, maxForPosition);
			}

			for (int end = fragmentLen; end <= sequenceLength; end++) {
				//
				int positionInMatrix = end % divisors[divisorsIt];

				modulo[dict[dnaSequence[end - 1] - 'A']][positionInMatrix]++;
				int maxForPosition = getMax(modulo[0][positionInMatrix], getMax(modulo[1][positionInMatrix], getMax(modulo[2][positionInMatrix], modulo[3][positionInMatrix])));
				updateTree(tree, 1, 0, divisors[divisorsIt] - 1, positionInMatrix, maxForPosition);

				if (end >= fragmentLen) {
					if (end > fragmentLen) {
						int positionInMatrix = (end - fragmentLen) % divisors[divisorsIt];
						modulo[dict[dnaSequence[end - fragmentLen - 1] - 'A']][positionInMatrix]--;
						int maxForPosition = getMax(modulo[0][positionInMatrix], getMax(modulo[1][positionInMatrix], getMax(modulo[2][positionInMatrix], modulo[3][positionInMatrix])));
						updateTree(tree, 1, 0, divisors[divisorsIt] - 1, positionInMatrix, maxForPosition);
					}

					preprocMatrix[end - fragmentLen + 1][end] = getMax(preprocMatrix[end - fragmentLen + 1][end], tree[1]);
				}
			}
		}
	}
}

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;
}