#include <iostream>
#include <fstream>
#include <cstring>

const int nmax = 610 ;

std::fstream in("perb.in", std::ios::in | std::ios::binary) ;
std::fstream out("perb.out", std::ios::out) ;

int n, m, i, j, k, l, x, y, sol, cate, nr[nmax][4], v[nmax], d[nmax][nmax] ;
char s[nmax] ;

inline int ce(char x)
{
    if (x == 'A')
    {
        return 0 ;
    }
    if (x == 'C')
    {
        return 1 ;
    }
    if (x == 'G')
    {
        return 2 ;
    }
    return 3 ;
}

int maxim()
{
    return std::max(nr[l][0], std::max(nr[l][1], std::max(nr[l][2], nr[l][3]))) ;
}

int main()
{
    in >> n >> m ;
    in >> (s + 1) ;
    for (i = 1 ; i <= n ; ++ i)
    {
        v[i] = ce(s[i]) ;
    }
    for (i = 1 ; i <= n ; ++ i)
    {
        for (j = i + 1 ; j <= n ; ++ j)
        {
            d[i][j] = j - i ;
        }
    }
    for (i = 1 ; i <= n ; ++ i)
    {
        for (j = 1 ; i + 2 * j - 1 <= n ; ++ j)
        {
            memset(nr, 0, sizeof(nr)) ;
            for (l = 0 ; l < j ; ++ l)
            {
                ++ nr[l][v[i + l]] ;
            }
            cate = 1 ;
            for (k = i + j ; k + j - 1 <= n ; k += j)
            {
                sol = 0 ;
                ++ cate ;
                for (l = 0 ; l < j ; ++ l)
                {
                    ++ nr[l][v[k + l]] ;
                    sol += cate - maxim() ;
                }
                d[i][k + j - 1] = std::min(d[i][k + j - 1], sol) ;
            }
        }
    }
    for (i = 1 ; i <= m ; ++ i)
    {
        in >> x >> y ;
        out << d[x][y] << '\n' ;
    }
}