#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][maxn][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;
		}
	}
	
	int half = (n>>1);
	for ( int divizor = 1 ; divizor <= half ; ++divizor ){
		
		int rest = 0;
		for ( int i = 0 ; i < n ; ++i ){
			
			++left[rest][i][ S[i] ];
			++rest; if ( rest == divizor )	rest = 0;
			
			if ( !i ) 	continue ;
			for ( int j = 0 ; j < divizor ; ++j ){
				for ( int k = 0 ; k < 4 ; ++k ){
					left[j][i][k] += left[j][i-1][k];
				}
			}
		}
		
		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 ){
					int m = 0;
					for ( int k = 0 ; k < 4 ; ++k ){
						m = left[rest][j][k]-left[rest][i ? i-1 : n][k] > m ? left[rest][j][k]-left[rest][i ? i-1 : n][k] : m;
					}
					now += b-m;
				}
				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 ){
				for ( int k = 0 ; k < 4 ; ++k ){
					left[j][i][k] = 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;
}