给定一个二进制字符串 $$$s_1s_2 \ldots s_n$$$,长度为 $$$n$$$。如果字符串 $$$s$$$ 仅由零和一组成,则称为二进制字符串。
对于字符串 $$$p$$$,我们将函数 $$$f(p)$$$ 定义为字符串 $$$p$$$ 中任何字符出现的最大次数。例如,$$$f(00110) = 3$$$,$$$f(01) = 1$$$。
您需要找到所有对 $$$1 \leq l \leq r \leq n$$$ 的总和 $$$f(s_ls_{l+1} \ldots s_r)$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是他们的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 二进制字符串的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的字符串,由$$$0$$$s和$$$1$$$s组成——二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出所有对 $$$1 \leq l \leq r \leq n$$$ 的总和 $$$f(s_ls_{l+1} \ldots s_r)$$$。
示例
输入复制
6102014011061100018100111001101011011100
输出复制
1 3 14 40 78 190
注意
在第一个测试用例中,字符串 $$$s$$$ 有一个子字符串,并且值 $$$f(0) = 1$$$。
在第二个测试用例中,字符串 $$$s$$$ 的所有子字符串都是 $$$0$$$、$$$01$$$、$$$1$$$。答案分别是$$$1 + 1 + 1 = 3$$$。
在第三个测试用例中,字符串 $$$s$$$ 的所有子字符串为 $$$0$$$、$$$01$$$、$$$011$$$、$$$0110$$$、$$$1$$$、$$$11$$$、$$$110$$$、$$$1$$$、$$$10$$$、 $$$0$$$。答案分别为 $$$1 + 1 + 2 + 2 + 1 + 2 + 2 + 1 + 1 + 1 = 14$$$。