CF1694B.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.

我们称一个长度为 $m$、下标从 $1$ 到 $m$ 的二进制字符串 $T$ 是“偏执的”（paranoid），如果可以通过以下两种操作中的任意一种，共执行 $m-1$ 次（顺序任意），将 $T$ 变为长度为 $1$ 的字符串：

• 选取 $T$ 中任意一个等于 01 的子串，并将其替换为 1；
• 选取 $T$ 中任意一个等于 10 的子串，并将其替换为 0。

例如，若 $T = $ 001，我们可以选取子串 $[T_2T_3]$ 并执行第一种操作，从而得到 $T = $ 01。

给定一个长度为 $n$、下标从 $1$ 到 $n$ 的二进制字符串 $S$，求满足 $1 \le l \le r \le n$ 的整数对 $(l, r)$ 的个数，使得 $S[l \ldots r]$（即 $S$ 中从第 $l$ 位到第 $r$ 位的子串）是一个偏执的字符串。

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$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示字符串 $S$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $S$，即 $S_1S_2 \ldots S_n$（对每个 $1 \le i \le n$，均有 $S_i = 0$ 或 $S_i = 1$）。

保证所有测试用例的 $n$ 值之和不超过 $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.

对于每个测试用例，输出满足条件的整数对 $(l, r)$ 的数量，其中 $1 \le l \le r \le n$，且 $S[l \ldots r]$（即字符串 $S$ 从位置 $l$ 到 $r$ 的子串）是一个 paranoid 字符串。

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).

在第一个样例中，$S$ 的长度已经是 $1$，因此无需执行任何操作。

在第二个样例中，$S$ 的所有子串都是“偏执的”（paranoid）。对于整个字符串，仅需执行第一种操作即可。

在第三个样例中，$S$ 的所有子串都是“偏执的”，除了子串 $[S_2S_3]$（因为无法对其执行任何操作）以及子串 $[S_1S_2S_3]$（即整个字符串）。