A15072. Paranoid String

Let's call a binary string $T$ of length $m$ indexed from $1$ to $m$ paranoid if we can obtain a string of length $1$ by performing the following two kinds of operations $m-1$ times in any order :

- Select any substring of $T$ that is equal to 01, and then replace it with 1.
- Select any substring of $T$ that is equal to 10, and then replace it with 0.For example, if $T = $ 001, we can select the substring $[T_2T_3]$ and perform the first operation. So we obtain $T = $ 01.

You are given a binary string $S$ of length $n$ indexed from $1$ to $n$ . Find the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$ ) is a paranoid string.

The first line contains an integer $t$ ( $1 \le t \le 1000$ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the size of $S$ .

The second line of each test case contains a binary string $S$ of $n$ characters $S_1S_2 \ldots S_n$ . ( $S_i = $ 0 or $S_i = $ 1 for each $1 \le i \le n$ )

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$ .

For each test case, output the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$ ) is a paranoid string.

In the first sample, $S$ already has length $1$ and doesn't need any operations.

In the second sample, all substrings of $S$ are paranoid. For the entire string, it's enough to perform the first operation.

In the third sample, all substrings of $S$ are paranoid except $[S_2S_3]$ , because we can't perform any operations on it, and $[S_1S_2S_3]$ (the entire string).