#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
 
using letter = uint8_t;
 
constexpr int maxn = 601;
constexpr int sigma = 4;
 
template <typename T>
using sir = array<T, maxn>;
 
void make_preproc(const int n, const sir<letter>& v, sir<sir<int16_t>>& d){
    sir<array<int, sigma>> frec_pe_rest = {};
    sir<int> frec_max_pe_rest = {}, sz_rest = {};
    int16_t cost_total = 0;
 
	for(int perioada = 1; 2*perioada <= n; ++perioada){
		for(int st = 1; st+perioada-1 <= n; ++st){
            for(auto& x : frec_pe_rest){
                fill(begin(x), end(x), (int)0); }
 
            fill(begin(frec_max_pe_rest), end(frec_max_pe_rest), (int)0);
            fill(begin(sz_rest), end(sz_rest), (int)0);
            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;
    sir<char> str;
    f.read(&str[1], n);
    sir<letter> 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; } }
 
    sir<sir<int16_t>> d;
    for(auto& x : d){
        for(auto& y : x){
            y = 1000; } }
 
    make_preproc(n, v, d);
 
    for(int i = 0, a, b; i < m; ++i){
        f >> a >> b;
        g << d[a][b] << '\n'; }
    return 0; }