题目描述

给定数组 $a_1,a_2,\dots,a_n$，数组每个元素取值为 $0$ 到 $9$。 如果一段子数组 $a_l,a_{l+1},\dots,a_r$ 满足子数组元素之和等于子数组的长度，即

就称该子数组为“好子数组”。

例如数组 $a=[1,2,0]$，一共有 $3$ 个好子数组：$a_{1\dots1}=[1]$、$a_{2\dots3}=[2,0]$、$a_{1\dots3}=[1,2,0]$。

请计算数组 $a$ 中好子数组的总数量。

输入

第一行一个整数 $t$（$1 \le t \le 1000$），代表测试用例组数。

每组测试用例： 第一行输入整数 $n$（$1 \le n \le 10^5$），代表数组长度。 第二行给出长度为 $n$ 的数字字符串，字符串第 $i$ 位字符对应 $a_i$ 的数值。

输出

对每组测试用例输出一个整数，表示该数组中好子数组的数量。

样例

3
3
120
5
11011
6
600005

3
6
1

说明

第一组样例就是题目描述举例，共 $3$ 个好子数组。

第二组样例共有 $6$ 个好子数组：$a_{1\dots1}$、$a_{2\dots2}$、$a_{1\dots2}$、$a_{4\dots4}$、$a_{5\dots5}$、$a_{4\dots5}$。

第三组样例仅有 $1$ 个好子数组：$a_{2\dots6}$。

数据范围

对于所有数据，$1 \le t \le 1000$，$1 \le n \le 10^5$，$0 \le a_i \le 9$

保证全部测试用例的 $n$ 之和不超过 $10^5$。

原题链接

原题链接