#include<stdio.h>

#define maxn 605
#define inf (1<<29)

FILE*f=fopen("perb.in","r");
FILE*g=fopen("perb.out","w");

int n,q;
int S[maxn],left[4][maxn>>1][maxn],D[maxn][maxn];
char sir[maxn];

inline int min ( const int &a , const int &b ){
	return a <= b ? a : b;
}

inline int max ( const int &a , const int &b ){
	return a >= b ? a : b;
}

int main () {
	
	fscanf(f,"%d %d\n",&n,&q);
	fscanf(f,"%s",&sir);
	for ( int i = 0 ; i < n ; ++i ){
		if ( sir[i] == 'A' )	S[i] = 0;
		else	if ( sir[i] == 'C' )	S[i] = 1;
		else	if ( sir[i] == 'G' )	S[i] = 2;
		else	S[i] = 3;
	}
	
	for ( int i = 0 ; i < n ; ++i ){
		for ( int j = i+1 ; j < n ; ++j ){
			D[i][j] = inf;
		}
	}
	
	int half = (n>>1);
	for ( int divizor = 1 ; divizor <= half ; ++divizor ){
		
		int rest = 0;
		for ( int i = 0 ; i < n ; ++i ){
			
			++left[ S[i] ][rest][i];
			++rest; if ( rest == divizor )	rest = 0;
			
			if ( !i ) 	continue ;
			for ( int j = 0 ; j < divizor ; ++j ){
				left[0][j][i] += left[0][j][i-1];
				left[1][j][i] += left[1][j][i-1];
				left[2][j][i] += left[2][j][i-1];
				left[3][j][i] += left[3][j][i-1];
			}
		}
		
		for ( int i = 0 ; i+(divizor<<1) <= n ; ++i ){
			int j = i+(divizor<<1)-1,b = 2;
			while ( j < n ){
				
				int now = 0;
				for ( int rest = 0 ; rest < divizor ; ++rest ){
					now += b-max(left[0][rest][j]-left[0][rest][i ? i-1 : n],max(left[1][rest][j]-left[1][rest][i ? i-1 : n],max(left[2][rest][j]-left[2][rest][i ? i-1 : n],left[3][rest][j]-left[3][rest][i ? i-1 : n])));
				}
				D[i][j] = min(D[i][j],now);
				
				j += divizor; ++b;
			}
		}
		
		for ( int i = 0 ; i < n ; ++i ){
			for ( int j = 0 ; j < divizor ; ++j ){
				left[0][j][i] = left[1][j][i] = left[2][j][i] = left[3][j][i] = 0;
			}
		}
	}
	
	int x,y;
	for ( int i = 1 ; i <= q ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		--x; --y;
		fprintf(g,"%d\n",D[x][y]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}