#include <bits/stdc++.h>

#define N_MAX 602
#define BUFFER_SIZE 100000

using namespace std;

FILE* fin = fopen("perb.in", "r");
ofstream fout ("perb.out");

char buffer[BUFFER_SIZE];
int pos = -1;

void read_buffer ()
{
    fread(buffer, sizeof(char), BUFFER_SIZE, fin);
}

char read_char ()
{
    pos++;
    if(pos == BUFFER_SIZE)
    {
        read_buffer();
        pos = 0;
    }
    return buffer[pos];
}

int read_int ()
{
    char c;
    while(!isdigit(c = read_char()));
    int ans = 0;
    while(isdigit(c))
    {
        ans = ans * 10 + c - '0';
        c = read_char();
    }
    return ans;
}

int n, m;

string s;

int cnt[N_MAX];
int dv[N_MAX][N_MAX];

int ans[N_MAX][N_MAX];

int cost[N_MAX][N_MAX][4];

int main()
{
    read_buffer();
    n = read_int();
    m = read_int();
    s.resize(n + 1);
    s[0] = ' ';
    for(int i = 1; i <= n; i++)
        s[i] = read_char();
    for(int i = 1; i <= n; i++)
        if(s[i] == 'A')
            s[i] = 'a';
        else if(s[i] == 'C')
            s[i] = 'b';
        else if(s[i] == 'T')
            s[i] = 'c';
        else
            s[i] = 'd';
    for(int i = 1; i <= n; i++)
        for(int k = 1; k <= n; k++)
            for(int c = 0; c < 4; c++)
            {
                if(i - k > 0)
                    cost[i][k][c] = cost[i - k][k][c];
                if(s[i] != char(c + 'a'))
                    cost[i][k][c]++;
            }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j * j <= i; j++)
            if(i % j == 0)
            {
                dv[i][++cnt[i]] = j;
                if(j == 1 || j * j == i)
                    continue;
                dv[i][++cnt[i]] = i / j;
            }
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
        {
            int lg = j - i + 1;
            ans[i][j] = n;
            for(int x = 1; x <= cnt[lg]; x++)
            {
                int d = dv[lg][x];
                int sum = 0;
                for(int k = 0; k < d; k++)
                {
                    int mi = n;
                    for(int c = 0; c < 4; c++)
                    {
                        int val = cost[j - k][d][c];
                        if(i - k - 1 > 0)
                            val -=cost[i - k - 1][d][c];
                        mi = min(mi, val);
                    }
                    sum += mi;
                }
                ans[i][j] = min(ans[i][j], sum);
            }
        }
    while(m--)
    {
        int l, r;
        l = read_int();
        r = read_int();
        fout << ans[l][r] << "\n";
    }
    return 0;
}