//
//  main.cpp
//  perb
//
//  Created by she on 05.12.2020.
//

#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' ;
	}
}