钢之位运算术师

英文题名：D. Fullmetal Bitchemist
来源：Codeforces 2237D
比赛：Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
时间限制：2 seconds
空间限制：256 megabytes

题目描述

给定一个二进制串。题目定义了“美丽子串”，要求统计整个字符串中的美丽子串数量。

输入格式

第一行输入 $t$。每组输入 $n$ 和长度为 $n$ 的二进制串 $s$。所有 $n$ 之和不超过 $10^6$。

输出格式

每组输出美丽子串数量。

样例

10
1
0
2
01
5
01001
3
001
6
011110
9
010110110
12
010000101001
16
1010011010010110
20
11110101101101001110
30
000101100011111001111100000010

1
2
10
5
15
30
47
81
139
316