#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("perb.in");
ofstream g("perb.out");
vector<int> divizori[605];
char s[605];
int freq[605][6];
int dp[605][605];
int code(char ch)
{
    if(ch=='A') return 0;
    if(ch=='C') return 1;
    if(ch=='G') return 2;
    if(ch=='T') return 3;
}
int main()
{

    int n,m;
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
      for(int j=i+1;j<=n;j++) dp[i][j]=1000;
    }
    f>>(s+1);

    for(int perioada=1;perioada<=n/2;perioada++)
    {
       for(int i=1;i<=perioada;i++)
       {
           for(int j=i;j<=n;j+=perioada)
           {
               for(int ch=0;ch<4;ch++)
               {
                   freq[j][ch]=freq[max(j-perioada,0)][ch];
               }
               freq[j][code(s[j])]++;
           }
       }

       for(int i=1;i<=n;i++)
       {
           for(int j=i+2*perioada-1;j<=n;j+=perioada)
           {int l=j-i+1;
           int nr=0;
               for(int d=j;d>=j-perioada+1;d--)
               {int maxim=0;
                   for(int ch=0;ch<4;ch++)
                   {
                    int fr=freq[d][ch]-freq[max(d-l,0)][ch];
                    maxim=max(maxim,fr);

                   }
                   nr=nr+l/perioada-maxim;
               }
               dp[i][j]=min(dp[i][j],nr);
           }
       }

    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        g<<dp[x][y]<<'\n';
    }

}