32276번 - 빨간점, 파란점 2

문제

원주 상에 동일한 간격으로 $N$개의 점이 배치되어 있다. 각 점은 빨간색 또는 파란색이고, 빨간 점이 2ドル$개 이상, 파란 점이 2ドル$개 이상 존재한다. 당신은 점들 사이를 현으로 이어 어떤 점도 적어도 하나의 현과 연결되도록 할 것이다. 이 때, 각 현이 잇는 두 점은 서로 같은 색깔이어야 한다.

당신의 목표는 끝점이 아닌 곳에서 교차하는 현의 쌍 개수를 최소화하는 것이다. 원주 상의 $N$개 점들의 색깔이 시계방향으로 주어질 때, 모든 점이 적어도 하나의 현과 연결되도록 하는 방법 중 교차하는 현의 쌍 개수의 최솟값을 출력하여라.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$ 가 주어지고,

이후 차례로 $T$ 개의 테스트 케이스가 주어진다. (1ドル \le T \le 1,483円$)

각 테스트 케이스의 첫 줄에는 정수 $N$이 주어진다 (4ドル \le N \le 500,000円$).

다음 줄에는 길이 $N$의 문자열이 주어진다. 문자열의 $i$번째 문자는 $N$개 점 중 임의로 정해진 하나의 점으로부터 시계방향으로 $i$번째 위치에 있는 점의 색깔을 나타낸다. R이면 빨간색 점, B이면 파란색 점임을 뜻한다. R의 개수 및 B의 개수는 2ドル$ 이상임이 보장된다.

모든 테스트 케이스에서 $N$의 합은 5ドル,000円,000円$을 넘지 않는다.

출력

각 테스트 케이스마다 첫 줄에는 “Case #$C$”를 출력하여야 한다. 이때 $C$는 테스트 케이스의 번호이다.

다음 줄에는 교차하는 현의 쌍 수의 최솟값을 출력한다.

제한

힌트