#include <algorithm>
#include <iostream>
#include <fstream>
#include <map>
 
#define MAX 610
#define pb push_back
 
using namespace std;
 
map <char, int> norm;
int n, q;
int ap[MAX][4];
short cost[MAX][MAX];
char strCit[2 * MAX];
 
int main()
{
    ifstream cin("perb.in");
    ofstream cout("perb.out");
 
    cin >> n >> q;
 
    cin >> strCit + 1;
 
    norm['A'] = 0;
    norm['C'] = 1;
    norm['G'] = 2;
    norm['T'] = 3;
    for (int i = 1; i <= n; i++)
        strCit[i] = norm[strCit[i]];
 
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            cost[i][j] = n;
 
    for (int st = 1; st <= n; st++)
        for (int div = 1; div <= (n - st + 1) / 2; div++)
        {
            for (int i = 0; i < div; i++)
                for (int k = 0; k < 4; k++)
                    ap[i][k] = 0;
 
            for (int p = 0; p < div; p++)
                ap[p][strCit[st + p]]++;
 
            for (int ul = st + div; ul + div <= n + 1; ul += div)
            {
                int c = ul - st + div;
                for (int p = 0; p < div; p++)
                {
                    ap[p][strCit[ul + p]]++;
 
                    int sc = 0;
                    for (int k = 0; k < 4; k++)
                        sc = (sc > ap[p][k])? sc : ap[p][k];
 
                    c -= sc;
                }
                cost[st][ul + div - 1] = (cost[st][ul + div - 1] > c)? c : cost[st][ul + div - 1];
            }
        }
 
    for (; q; q--)
    {
        int x, y;
        cin >> x >> y;
 
        cout << cost[x][y] << '\n';
    }
 
    cin.close();
    cout.close();
    return 0;
}