#include <fstream>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;

constexpr int maxn = 601;
constexpr int sigma = 4;

void make_preproc(const int n, const uint8_t v[maxn], uint16_t d[maxn][maxn]){
	memset(d, 0x7F, maxn * maxn * sizeof(uint16_t));

	uint16_t frec_pe_rest[maxn][4] = {}, frec_max_pe_rest[maxn] = {}, sz_rest[maxn] = {};
	uint16_t cost_total = 0;

	for(int perioada = 1; perioada <= n; ++perioada){
		for(int st = 1; st <= n; ++st){
			memset(frec_pe_rest, 0, maxn*4*sizeof(uint16_t));
			memset(frec_max_pe_rest, 0, maxn*sizeof(uint16_t));
			memset(sz_rest, 0, maxn*sizeof(uint16_t));
			cost_total = 0;

			for(int dr = st, rest = 1%perioada; dr <= n; ++dr, ++rest){
				if(rest >= perioada){
					rest -= perioada; }

				cost_total -= sz_rest[rest] - frec_max_pe_rest[rest];

				++sz_rest[rest], ++frec_pe_rest[rest][v[dr]];
				frec_max_pe_rest[rest] = max(frec_max_pe_rest[rest], frec_pe_rest[rest][v[dr]]);

				cost_total += sz_rest[rest] - frec_max_pe_rest[rest];

				if(rest == 0 && dr-st+1 != perioada){
					d[st][dr] = min(d[st][dr], cost_total); } } } } }

int main(){
	ifstream f("perb.in");
	ofstream g("perb.out");
	int n, m;
	f >> n >> m >> ws;

	char str[maxn];
	f.read(&str[1], n);

	uint8_t v[maxn];

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

	uint16_t d[maxn][maxn];

	make_preproc(n, v, d);

	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		g << d[a][b] << '\n'; }
	return 0; }