#include <bits/stdc++.h>

#define N_MAX 602

using namespace std;

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()
{
    ifstream fin ("perb.in");
    ofstream fout ("perb.out");
    fin >> n >> m;
    fin >> s;
    s = " " + s;
    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;
        fin >> l >> r;
        fout << ans[l][r] << "\n";
    }
    return 0;
}