빨간점, 파란점 2

원주 위에 같은 간격으로 $N$개의 점이 놓여 있다. 각 점은 빨간색 또는 파란색이고, 빨간 점과 파란 점은 각각 2개 이상 있다. 점들을 현으로 이어서 모든 점이 적어도 하나의 현과 연결되도록 한다. 이때 각 현이 잇는 두 점은 색깔이 같아야 한다.

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

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이후 $T$개의 테스트 케이스가 차례로 주어진다 ($1 \le T \le 1\,483$).

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

다음 줄에는 길이 $N$의 문자열이 주어진다. 문자열의 $i$번째 문자는 임의로 정한 기준점에서 시계 방향으로 $i$번째에 있는 점의 색깔이다. R은 빨간 점, B는 파란 점을 뜻한다. R의 개수와 B의 개수는 모두 2 이상임이 보장된다.

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

각 테스트 케이스마다 첫 줄에 "Case #$C$"를 출력한다. 여기서 $C$는 테스트 케이스의 번호이다. 다음 줄에는 교차하는 현 쌍 수의 최솟값을 출력한다.