#include <fstream>

using namespace std;
ifstream cin ("perb.in");
ofstream cout ("perb.out");
int sp[4][605];
int ans[605][605];
int cod[30];
int maxi[605];
char vc[605];
int main()
{
    int n, m, i, j, d, s = 0;
    cin >> n >> m;
    cin >> vc + 1;
    cod[0] = 0;
    cod[2] = 1;
    cod['G' - 'A'] = 2;
    cod['T' - 'A'] = 3;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            ans[i][j] = 1e9;
    for (i = 1; i <= n; i++)
        for (d = 1; d <= n - i + 1; d++)
        {
            for (j = 0; j < d; j++)
            {
                maxi[j] = 0;
                for (int h = 0; h < 4; h++)
                    sp[h][j] = 0;
            }
            s = 0;
            for (j = i; j <= n; j++)
            {
                sp[cod[vc[j] - 'A']][j % d]++;
                s -= maxi[j % d];
                maxi[j % d] = max (maxi[j % d], sp[cod[vc[j] - 'A']][j % d]);
                s += maxi[j % d];
                if ((j - i + 1) % d == 0 && j - i + 1 > d)
                    ans[i][j] = min (ans[i][j], (j - i + 1) - s);
            }
        }
    while (m)
    {
        int x, y;
        cin >> x >> y;
        cout << ans[x][y] << '\n';
        m--;
    }
    return 0;
}