#include <cstdio>
#include <algorithm>

#define DIM (1<<10)
#define INF (1<<30)
using namespace std;

int N, M, X, Y;
int D[5][DIM];
int F[DIM][DIM];
int R[DIM][DIM];

char S[DIM];

int main(){

	freopen("perb.in" ,"r", stdin );
	freopen("perb.out","w", stdout);

	scanf("%d %d", &N, &M);
	scanf("%s", S + 1);

	for(int k = N / 2; k >= 1; k --){
		for(int i = 1; i <= k; i ++){
			for(int j = i; j <= N; j += k){
				switch(S[j]){
					case 'A':{D[1][j] = 0; D[2][j] = 1; D[3][j] = 1; D[4][j] = 1; break;}
					case 'C':{D[1][j] = 1; D[2][j] = 0; D[3][j] = 1; D[4][j] = 1; break;}
					case 'G':{D[1][j] = 1; D[2][j] = 1; D[3][j] = 0; D[4][j] = 1; break;}
					case 'T':{D[1][j] = 1; D[2][j] = 1; D[3][j] = 1; D[4][j] = 0; break;}
				} 
				if(j != i){
					D[1][j] += D[1][j-k];
					D[2][j] += D[2][j-k];
					D[3][j] += D[3][j-k];
					D[4][j] += D[4][j-k];
				}
			}
		}
		for(int p = 1; p <= N - k * 2 + 1; p ++){
			for(int u = p + k * 2 - 1; u <= N; u += k){
				if(F[p][u] == 0){
					
					F[p][u] = 1; 
					int sum = 0;
					
					for(int i = p; i < p + k; i ++){
						int minim = INF, val;

						val = D[1][u - (k - (i - p)) + 1];
						if(i - k >= 1) val -= D[1][i-k];
						if(minim > val) minim = val;
					
						val = D[2][u - (k - (i - p)) + 1];
						if(i - k >= 1) val -= D[2][i-k];
						if(minim > val) minim = val;

						val = D[3][u - (k - (i - p)) + 1];
						if(i - k >= 1) val -= D[3][i-k];
						if(minim > val) minim = val;

						val = D[4][u - (k - (i - p)) + 1];
						if(i - k >= 1) val -= D[4][i-k];
						if(minim > val) minim = val;

						sum += minim;
					}
					R[p][u] = sum;
				}
			}
		}
	}

	for(int i = 1; i <= M; i ++){
		scanf("%d %d", &X, &Y);
		printf("%d\n", R[X][Y]);
	}

	fclose(stdin );
	fclose(stdout);

	return 0;
}