#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){
	memset(&d[0][0], 0x7F, maxn*maxn * 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; 2*perioada <= n; ++perioada){
        for(int st = 1; st+perioada-1 <= 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; }