선거

오늘은 어느 슈퍼히어로 팀이 최고인지 정해야 한다. 캡 팀인가, 아이언맨(토니) 팀인가. $N$명의 화난 팬이 있으며, 각자 좋아하는 팀에 투표해야 한다. 투표지는 'C'(캡) 또는 'T'(토니) 중 하나다.

캡은 이길 가능성이 없다. 그는 정직한 사람이라서 선거 부정을 저지르기로 한다. 무효로 만드는 표의 수를 최소로 하려고 한다.

개표는 두 번 진행된다.

• 팬 번호 오름차순으로, 무효 처리된 표를 제외하고 센다.
• 팬 번호 내림차순으로, 무효 처리된 표를 제외하고 센다.

개표 중 어느 시점에서든 캡이 토니에게 뒤지지 않으면 캡은 만족한다. 동점은 괜찮지만, 표가 적은 순간이 있으면 안 된다.

하지만 누구도 토니를 건드릴 수 없다. 토니는 캡의 계획을 알고 있으며, $Q$개의 시나리오마다 캡이 무효로 만들 표의 수를 알고 싶어 한다. 각 시나리오는 $L$과 $R$로 주어지며, 번호가 $L$부터 $R$까지인(양 끝 포함) 팬만 투표에 참여한다.

첫째 줄에 팬의 수 $N$이 주어진다. 둘째 줄에는 각 팬의 투표를 나타내는 길이 $N$의 문자열이 주어진다. 문자는 'C' 또는 'T'이다. 셋째 줄에는 시나리오의 수 $Q$가 주어진다. 다음 $Q$개 줄에는 각각 두 정수 $L$과 $R$($1 \le L \le R \le N$)이 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 시나리오의 답을 출력한다.

첫 번째 시나리오에서 투표는 CCCTTTTTTCC이다. 유일한 해는 토니의 표 4개를 무효로 만드는 것이다.

두 번째 시나리오에서 투표는 TTTTTT이다. 유일한 해는 모든 표를 무효로 만드는 것이다.

세 번째 시나리오에서 투표는 CCCTTT이다. 유일한 해는 토니의 표를 전부 무효로 만드는 것이다.