You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

我们规定, 在一个序列中出现次数最多的那个数字就是重数, 如果有多个数字出现次数最多且相同, 则这些数字都是重数.

题目描述

给你一个 01 字符串, 只由数字 0 和 1 构成, 我们想知道, 在所有的 $[l, r]$ 串中, 重数种类之和是多少?

例如:

10 的重数种类之和是 $4$

长度为 $1$ 的子串 1 的重数种类只有 $1$ 个, 子串 0 的重数种类只有 $1$ 个

长度为 $2$ 的子串 10 的重数种类有 1 和 0 两个

例如:

1100 的重数种类之和是 $12$

长度为 $1$ 的子串 1, 1, 0, 0 的重数种类之和为 $4$个

长度为 $2$ 的子串 11, 10, 00 的重数种类为 $1, 2, 1$ 个, 总数量也是 $4$ 个

长度为 $3$ 的子串 110, 100 的重数种类为 $1, 1$个, 总数量是 $2$ 个

长度为 $4$的子串 1100 的重数种类为 $2$ 个

一共是 $12$ 个

输入格式

第一行一个整数 $t$ 表示有 $t$ 组数据

接下来 $t$ 组数据, 每组数据的第一行是一个整数 $n$ 表示 01 串的长度

第二行为一个长度为 $n$ 的 01 串

输出格式

输出 $t$ 行, 每行一个整数表示每个样例的重数种类之和.

样例 #1

样例输入 #1

3
2
10
4
1100
5
10101

样例输出 #1

4
12
21

提示

• $2 \le t \le 10$
• 对于 $40\%$ 的数据 $1 \le n \le 10^3$
• 对于 $100\%$ 的数据 $1 \le n \le 10^5$