题目描述

对一个字符串 $S$ ，有以下两种操作：

• 将子串 $01$ 替换为 $1$
• 将子串 $10$ 替换为 $0$

总共 $t$ 组数据，每组的 $S$ 都是一个给定长度为 $n$ 的 $01$ 串。求 $S$ 的子串个数，满足经过若干次操作，可将该子串长度变为 $1$ 。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) 表示测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ 表示 $S$ 的长度。

每个测试用例的第二行包含一个由 $n$ 个字符 $S_1S_2 \ldots S_n$ 组成的二进制字符串 $S$ 。( 其中$S_i = 0 或 S_i = 1$)

输出

针对每个测试用例，$S[l \ldots r]$ （ $S$ 从 $l$ 到 $r$ 的子串）是一个符合要求的字符串，最后输出满足要求的 $(l, r)$ 对的数量 $(1 \le l \le r \le n)$ 。

样例

5
1
1
2
01
3
100
4
1001
5
11111

1
3
4
8
5

样例解释

对于字符串$"1001"$，共有以下8种满足条件的子串

1
0
0
1
10
01
001
1001

数据范围

• $1 \le t \le 1000$
• $1 \le n \le 2\times 10^5$
• $\sum n \le 2\times 10^5$

$1 \le n \le 2 \cdot 10^5$，保证所有测试用例的 $n$ 总和不超过 $2 \cdot 10^5$ 。（如果你觉得自己的代码没有问题但是始终出错的时候请在此稍作思索^ ^）