题目描述

给定一个由 $0$ 到 $9$ 的整数组成的数组 $a_1, a_2, \dots, a_n$。

如果一个子数组 $a_l, a_{l+1}, \dots, a_r$ 的元素之和等于该子数组的长度（即 $\sum_{i=l}^r a_i = r - l + 1$），我们称其为好子数组。

例如，如果 $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$）—— 数组 $a$ 的长度。
• 第二行包含一个长度为 $n$ 的数字字符串，其中第 $i$ 个字符表示 $a_i$ 的值。

输出格式

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

样例输入 1

3
3
120
5
11011
6
600005

样例输出 1

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}$（元素依次为 $0, 0, 0, 0, 5$，其和为 $5$，子数组长度也为 $5$）。

数据范围

• 对于所有测试点，保证 $1 \le t \le 1000$。
• 对于每个测试用例，保证 $1 \le n \le 10^5$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $10^5$。
• 保证给定的字符串仅由数字 0 到 9 组成。