// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
int n,q; string s;
struct segment_Tree
{
vector<int> erase[N<<2];
vector<pair<int,int>> erasList[N<<2];
int T[N<<2][3] , sv[N<<2]; bool mrk[N];
void calc_erase (int nd , int l , int r)
{
for (int i=l; i<=r; i++) mrk[i] = false;
for (int i=l; i<=r; i++)
{
if (s[i] == 'C') T[nd][0]++;
else if (T[nd][0] > 0) T[nd][0]--;
else
{
mrk[i] = true;
erase[nd].push_back(i);
}
}
for (int i=r; i>=l; i--)
{
if (s[i] == 'C') T[nd][1]++;
else if (T[nd][1] > 0) T[nd][1]--;
else T[nd][2]++;
}
int out = 0 , k = 0;
for (int i=r; i>=l; i--)
{
if (mrk[i])
{
erasList[nd].push_back({out,k});
continue;
}
if (s[i] == 'C') k++;
else if (k > 0) k--;
else out++;
}
reverse(erasList[nd].begin(),erasList[nd].end());
}
void build (int nd , int l , int r)
{
fill_n(T[nd],3,0);
if (l == r)
{
calc_erase(nd , l , r);
return;
}
int m = l+r >> 1;
build(nd<<1 , l , m);
build((nd<<1)+1 , m+1 , r);
calc_erase(nd , l , r);
}
pair<int,int> NOerase_ouT (int nd , int l , int r , int lq , int rq , int k)
{
if (lq<=l and r<=rq)
{
sv[nd] = erase[nd].size();
if (sv[nd] > k) sv[nd] -= k , k = 0;
else k -= sv[nd] , sv[nd] = 0;
return {sv[nd] , k+T[nd][0]};
}
if (r<lq or l>rq) return {0,k};
int m = l+r >> 1;
auto [el,kl] = NOerase_ouT(nd<<1 , l , m , lq , rq , k);
sv[nd] = el , k = kl;
auto [er,kr] = NOerase_ouT((nd<<1)+1 , m+1 , r , lq , rq , k);
sv[nd] += er; k = kr;
return {sv[nd] , k};
}
pair<int,int> rv_NOerase_ouT (int nd , int l , int r , int lq , int rq , int k)
{
if (lq<=l and r<=rq)
{
int e = T[nd][2];
if (e > k) e -= k , k = 0;
else k -= e , e = 0;
return {e , k+T[nd][1]};
}
if (r<lq or l>rq) return {0,k};
int m = l+r >> 1 , e = 0;
auto [er,kr] = rv_NOerase_ouT((nd<<1)+1 , m+1 , r , lq , rq , k);
e += er , k = kr;
auto [el,kl] = rv_NOerase_ouT(nd<<1 , l , m , lq , rq , k);
e += el , k = kl;
return {e , k};
}
pair<int,int> rv_optimize (int nd , int l , int r , int lq , int rq , int k)
{
int m = l+r >> 1 , e = 0;
if (lq<=l and r<=rq)
{
int sz = erase[nd].size() , rlimit;
if (sv[nd] == 0) rlimit = rq;
else rlimit = erase[nd][sz-sv[nd]]-1;
if (rlimit >= lq)
{
if (sv[nd] > 0)
{
auto [er,kr] = erasList[nd][sz-sv[nd]];
if (er >= k) e=er-k , k=kr;
else k-=er , e=0 , k+=kr;
}
auto [el,kl] = rv_NOerase_ouT(nd , l , r , lq , rlimit , k);
e += el , k = kl;
return {e , k};
}
else return erasList[nd][sz-sv[nd]];
}
if (r<lq or l>rq) return {0,k};
auto [er,kr] = rv_optimize((nd<<1)+1 , m+1 , r , lq , rq , k);
e += er , k = kr;
auto [el,kl] = rv_optimize(nd<<1 , l , m , lq , rq , k);
e += el , k = kl;
return {e , k};
}
} sT;
void iN ()
{
cin >> n >> s >> q;
s = 'T'+s;
}
void ouT ()
{
while (q--)
{
int l,r; cin >> l >> r;
int out = sT.NOerase_ouT(1,1,n,l,r,0).first;
out += sT.rv_optimize(1,1,n,l,r,0).first;
cout << out << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
iN ();
sT.build(1,1,n);
ouT ();
}
