给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。我们将最大子串定义为在保持所有元素相等的情况下无法扩展的子串。例如,在字符串 $$$11000111$$$ 中,存在三个最大子字符串:$$$11$$$、$$$000$$$ 和 $$$111$$$。
在一次操作中,您最多可以选择两个相邻子字符串。由于它们是最大且相邻的,因此很容易看出它们的元素必须具有不同的值。设 $$$a$$$ 为 1 序列的长度,$$$b$$$ 为 0 序列的长度。然后执行以下操作:
- 如果 $$$a \ge b$$$,则用 $$$b$$$ 替换 $$$b$$$ 选定的零。
- 如果 $$$a < b$$$,则将 $$$a$$$ 所选内容替换为 $$$a$$$ 零。
例如,对于 $$$1110000$$$,我们将其设为 $$$0000000$$$,对于 $$$0011$$$,我们将其设为 $$$1111$$$。如果一个字符串可以使用上述操作任意次数(可能为零)转换为 $$$1111...1111$$$,我们称该字符串为良好字符串。求$$$s$$$的所有$$$\frac{n(n+1)}{2}$$$非空子串中好子串的数量。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 好子串的数量。
示例
输入 #1
4 6 100011 3 101 5 11111 6 010101
输出 #1
8 5 15 18
注意
让我们定义从索引 $$$l$$$ 到索引 $$$r$$$ 的子字符串 $$$[l, r]$$$。
对于第一个测试用例,好的子字符串是:
- $$$[1,1]$$$,
- $$$[1,2]$$$,
- $$$[3,6]$$$,
- $$$[4,5]$$$,
- $$$[4,6]$$$,
- $$$[5,5]$$$,
- $$$[5,6]$$$,
- $$$[6,6]$$$.
在第二个测试用例中,除了 $$$[2,2]$$$ 之外的所有子字符串都很好。
在第三个测试用例中,所有子字符串都很好。