Red and Blue Dots 2

Points on a circle are placed at equal intervals, $N$ points in total. Each point is red or blue, and there are at least two red points and at least two blue points. Connect the points with chords so that every point is joined to at least one chord. Each chord must join two points of the same color.

The goal is to minimize the number of pairs of chords that cross at a point that is not an endpoint of either chord. Given the colors of the $N$ points in clockwise order, output the minimum number of crossing pairs over all valid ways to connect every point to at least one chord.

The first line contains the number of test cases $T$. Then $T$ test cases follow, one after another ($1 \le T \le 1\,483$).

The first line of each test case contains an integer $N$ ($4 \le N \le 500\,000$).

The next line contains a string of length $N$. The $i$-th character of the string is the color of the point that is $i$ steps clockwise from a point chosen arbitrarily as the reference. R means a red point and B means a blue point. The number of R and the number of B are each guaranteed to be at least 2.

The sum of $N$ over all test cases does not exceed $5\,000\,000$.

For each test case, print a line "Case #$C$", where $C$ is the test case number. On the next line, print the minimum number of pairs of chords that cross.