给定一个数组 $$$a_1, a_2, \dots , a_n$$$,由从 $$$0$$$ 到 $$$9$$$ 的整数组成。如果子数组 $$$a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r$$$ 是好的,如果该子数组的元素总和等于该子数组的长度 ($$$\sum\limits_{i=l}^{r} a_i = r - l + 1$$$)。
例如,如果 $$$a = [1, 2, 0]$$$,则有 $$$3$$$ 好的子数组:$$$a_{1 \dots 1} = [1]、a_{2 \dots 3} = [2, 0]$$$ 和 $$$a_{1 \dots 3} = [1, 2, 0]$$$。
计算数组$$$a$$$的好子数组的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含一个由 $$$n$$$ 十进制数字组成的字符串,其中第 $$$i$$$ 数字等于 $$$a_i$$$ 的值。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印一个整数 — 数组 $$$a$$$ 的好子数组的数量。
示例
输入 #1
3 3 120 5 11011 6 600005
输出 #1
3 6 1
注意
声明中考虑了第一个测试用例。
在第二个测试用例中,有 $$$6$$$ 好的子数组:$$$a_{1 \dots 1}$$$、$$$a_{2 \dots 2}$$$、$$$a_{1 \dots 2}$$$、$$$a_{4 \dots 4}$$$、$$$a_{5 \dots 5}$$$ 和$$$a_{4 \点5}$$$。
在第三个测试用例中,只有一个好的子数组:$$$a_{2 \dots 6}$$$。