#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[maxn>>1][4],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;
		}
	}
	
	for ( int i = 0 ; i < n ; ++i ){
		
		for ( int divizor = 1 ; (i+(divizor<<1)) <= n ; ++divizor ){
			
			for ( int j = 0 ; j < divizor ; ++j ){
				for ( int k = 0 ; k < 4 ; ++k ){
					left[j][k] = 0;
				}
			}
			
			int rest = 0,b = 0;
			++left[0][S[i]];
			for ( int j = i+1 ; j < n ; ++j ){
				
				++rest;
				if ( rest == divizor )	rest = 0,++b;
				
				++left[rest][S[j]];
				
				if ( rest == divizor-1 && b >= 1 ){
					
					int now = 0;
					for ( int r = 0 ; r < divizor ; ++r ){
						
						int m = 0;
						for ( int k = 0 ; k < 4 ; ++k ){
							m = max(m,left[r][k]);
						}
						now += b-m+1;
					}
					D[i][j] = min(D[i][j],now);
				}
			}
		}
	}
	
	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;
}