#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("perb.in");
ofstream fout ("perb.out");

#define MAX 600

int n, m, x, y, rez[MAX + 1][MAX + 1], a[5][MAX + 1], sum;
char c[MAX + 1], w;

int main ()
{
    fin >> n >> m;

    fin >> (c + 1);
    fout << c;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)rez[i][j] = 100000000;

    for (int i = n / 2; i >= 1; i--)
    {
        for (int j = 1; j <= n; j++)
        {
            if (c[j] == 'A')
            {
                a[1][j] = 0;
                a[2][j] = 1;
                a[3][j] = 1;
                a[4][j] = 1;
            }
            else if (c[j] == 'C')
            {
                a[1][j] = 1;
                a[2][j] = 0;
                a[3][j] = 1;
                a[4][j] = 1;
            }
            else if (c[j] == 'G')
            {
                a[1][j] = 1;
                a[2][j] = 1;
                a[3][j] = 0;
                a[4][j] = 1;
            }
            else if (c[j] == 'T')
            {
                a[1][j] = 1;
                a[2][j] = 1;
                a[3][j] = 1;
                a[4][j] = 0;
            }

            if (j >= i)
            {
                a[1][j] += a[1][j - i];
                a[2][j] += a[2][j - i];
                a[3][j] += a[3][j - i];
                a[4][j] += a[4][j - i];
            }
        }

        int val;
        for (int i1 = 1; i1 <= n - i + 1; i1++)
        {
            for (int j1 = i1 + i * 2 - 1; j1 <= n; j1 += i)
            {
                sum =0;
                for (int p = j1 - i + 1; p <= j1; p++)
                {
                    val = a[1][p] - a[1][max(0, i1 - j1 + p - 1)];
                    val = min(a[2][p] - a[2][max(0, i1 - j1 + p - 1)], val);
                    val = min(a[3][p] - a[3][max(0, i1 - j1 + p - 1)], val);
                    val = min(a[4][p] - a[4][max(0, i1 - j1 + p - 1)], val);

                    sum += val;
                }
                rez[i1][j1] = min(sum, rez[i1][j1]);
            }
        }
    }

    for (int i = 1; i <= n; i++)rez[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        fout << rez[x][y] << '\n';
    }
    return 0;
}