#include <iostream>
#include <fstream>
#include <cstdlib>
#include <math.h>

using namespace std;

int N;
char str[613];

int MAX_STRIDE;

int DIVISORS[611][610];
int Q[4][611][1221];

static void initDiv() {
	for (int i=1; i<=N; i++) {
		int ndiv = 0;
		int maxJ = 1+(int)ceil(sqrt(N));
		for (int j=1; j <= maxJ; j++) {
			if (i % j == 0) {
				if (j != i) DIVISORS[i][ndiv++] = j;
				if (j != 1) DIVISORS[i][ndiv++] = i/j;
			}
		}

		DIVISORS[i][ndiv] = 0;
	}
}

static void initStr() {
	for (int i=0; i<N; i++) {
		switch (str[i]) {
			case 'A': str[i] = 0; break;
			case 'C': str[i] = 1; break;
			case 'G': str[i] = 2; break;
			case 'T': str[i] = 3; break;
		}
	}
}

static void initChars() {
	MAX_STRIDE = N/2;

	for (int i=0; i<4; i++) {
		for (int stride = MAX_STRIDE; stride >= 1; stride--) {
			for (int p = 2*N; p >= N; --p)
				Q[i][stride][p] = 0;

			for (int p = N-1; p >=0; --p) {
				Q[i][stride][p] = (str[p] == i) + Q[i][stride][p+stride];

				//cout << "Q" << i << " " << stride << " " << p << " " = Q[i][stride][p] << "\n";

				
			}
		}
	}
}

static void init() {
	initDiv();
	initStr();
	initChars();
}

static inline int chars(int c, int base, int len, int stride) {
	return Q[c][stride][base] - Q[c][stride][base+len];
}

static inline int maxc(int base, int len, int stride) {
	int mx = 0;
	for (int i=0; i<4; i++) {
		int cand = chars(i, base, len, stride);
		if (cand > mx) mx = cand;
	}

	return mx;
}

static int query(int base, int len) {
	int best = 0;

	for (int id=0; id<=N; id++) {
		int div = DIVISORS[len][id];
		if (!div) break;

		int cost = 0;
		for (int i = 0; i<div; i++) {
			cost -= maxc(base+i, len, div);
		}

		if (cost < best) best = cost;
	}

	return len+best;
}

int main(int argc, char** argv) {
	ifstream fIn("perb.in");
	ofstream fOut("perb.out");

	int M;
	fIn >> N >> M;
	fIn >> str;

	init();

	for (int i=0; i<M; i++) {
		int a,b;

		fIn >> a >> b;
		fOut << query(a-1,1+b-a) << "\n";
	}
	
	fOut.close();	
}