当前没有测试数据。

题目描述

给你一个长度为 $n$ 的二进制字符串 $s1s2\ldots sn$。二进制字符串的定义是仅由数字 $0$ 和 $1$ 组成的字符串。

对于一个字符串 $p$，我们定义函数 $f(p)$ 为字符串 $p$ 中出现次数最多的字符的出现次数。例如，$f(00110)=3$，$f(01)=1$。

你需要求出所有满足 $1 \le l \le r \le n$ 的子串 $slsl+1\ldots sr$ 对应的 $f$ 值之和。

数据范围

• 时间限制：每个测试点 $2$ 秒
• 内存限制：每个测试点 $256$ 兆字节

输入格式

输入包含多组测试用例。 第一行输入一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。 接下来依次给出每组测试用例的描述：

• 每组测试用例的第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 二进制字符串的长度。
• 第二行输入一个长度为 $n$ 的字符串 $s$ —— 仅由 $0$ 和 $1$ 组成的二进制字符串。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试用例，输出所有子串的 $f$ 值之和。

样例输入

6
1
0
2
01
4
0110
6
110001
8
10011100
11
01011011100

样例输出

1
3
14
40
78
190

说明/提示

• 第一个测试用例中，字符串仅有一个子串，$f(0)=1$，答案为 $1$。
• 第二个测试用例中，字符串的所有子串为 $0$、$01$、$1$，对应的 $f$ 值分别为 $1$、$1$、$1$，答案为 $3$。
• 第三个测试用例中，字符串的所有子串为 $0$、$01$、$011$、$0110$、$1$、$11$、$110$、$1$、$10$、$0$，对应的 $f$ 值分别为 $1$、$1$、$2$、$2$、$1$、$2$、$2$、$1$、$1$、$1$，答案为 $14$。