#include <cstdio>
#include <cstring>
#include <ctime>

int N, M;
char S[606];
int A[606][606][4];
int B[606][606];

inline int max(int a, int b) { return a>b?a:b; }
inline int min(int a, int b) { return a<b?a:b; }

int cod(char C)
{
 switch (C)
	{
	 case 'A' : return 0;
	 case 'C' : return 1;
	 case 'G' : return 2;	 
	}
 return 3;
}

void build()
{
 int i, j, d;

 for (d=1; d*2<=N; ++d)
	 for (i=0; i<d; ++i)
		{
		 A[d][i][0] = A[d][i][1] = A[d][i][2] = A[d][i][3] = 0;
		 ++A[d][i][cod(S[i])];
		 for (j=i+d; j<N; j+=d)
			{
			 memcpy(A[d][j], A[d][j-d], sizeof(A[d][j-d]));
			 ++A[d][j][cod(S[j])];
			}
		}			 
}

void compute()
{
 int i, j, d, k, kk, a, aux;
 
 memset(B, 0x3f, sizeof(B));
 for (d=1; d*2<=N; ++d)
	for (i=0; i<N; ++i)				 
	 	 for (j=i+d; j+d<=N; j+=d)
			{
			 aux = 0;
			 for (k=0; k<d; ++k)
				{	
				 for (kk=a=0; kk<4; ++kk)
					 if (i+k>d) a = max(a, A[d][j+k][kk] - A[d][i+k-d][kk]);				 
						else a = max(a, A[d][j+k][kk]);
				 aux += ((j-i)/d+1) - a;
				 if (aux > B[i][j+d]) break;
				}
			 B[i][j+d] = min(B[i][j+d], aux);
			}
}

int main()
{
 int x, y;
 double f = clock();

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

 scanf("%d %d\n", &N, &M);
 scanf("%s", &S);
 //fgets(S, N, stdin);
 
 build();
/*
 for (int d=1; d*2<=N; ++d, printf("\n"))
	for (int i=0; i<N; ++i)
		printf("%d ",A[d][i][0]);
*/
 compute();
/*
 for (int i=0; i<N; ++i, printf("\n"))
	 for (int j=i+1; j<N; ++j)
		 printf("%d ",B[i][j]);
  */
 while (M--)
	{
	 scanf("%d %d", &x, &y);
	 printf("%d\n", B[x-1][y]);
	}


 printf("%.5lf\n", (clock()-f)/CLOCKS_PER_SEC);
 return 0;
}