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

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

template <int dim>
class parsator{
	ifstream& f;
	array<char, dim> buf;
	char *poz, *last;
	void reload(){
		if(poz >= last){
			poz = &buf[0];
			f.read(&buf[0], dim); } }
public:
	parsator(ifstream& ff): f(ff){
		last = &buf[0] + dim;
		poz = last;
		reload(); }

	parsator<dim>& operator>>(int& rhs){
		rhs = 0;
		while(!isdigit(*poz)){
			++poz;
			reload(); }
		while(isdigit(*poz)){
			rhs *= 10;
			rhs += *poz-'0';
			++poz;
			reload(); }
		return *this; } };


void make_preproc(const int n, const array<uint8_t, maxn>& v, array<array<uint16_t, maxn>, maxn>& d){
	for(int i = 0; i <= n; ++i){
		memset(&d[i][i], 0x7F, (maxn-i+1) * sizeof(uint16_t)); }

	array<array<uint16_t, 4>, maxn> frec_pe_rest;
	array<uint16_t, maxn> frec_max_pe_rest, sz_rest;
	uint16_t cost_total;;

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

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

				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;

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

	array<uint8_t, maxn> v;

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

	array<array<uint16_t, maxn>, maxn> d;

	make_preproc(n, v, d);

	parsator<1000> ps(f);

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