给定一个 $1$ 到 $n$ 的随机排列。换句话说，每个从 $1$ 到 $n$ 的数字恰好出现一次，且它们的顺序是随机的。

我们寻找“有趣的区间”，即区间内元素之和等于其长度平方的区间。形式化地，在序列 $a_1, a_2, \dots, a_n$ 中，一个有趣的区间对应于索引范围 $[p, q]$ ($1 \le p \le q \le n$)，满足：

$$\sum_{i=p}^{q} a_i = (q - p + 1)^2$$

计算有趣的区间数量。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 200,000$)，表示测试用例的数量。每个测试用例由两行描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 200,000$)，表示序列的长度。

每个测试用例的第二行包含 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n, a_i \neq a_j$ 当 $i \neq j$ 时)。

该序列是随机选择的，意味着 $n!$ 种序列中的每一种被选中的概率相等，且不同测试用例之间相互独立。然而，组织者可以在每个测试用例中任意选择 $t$ 的值和 $n$ 的值。

所有测试用例的 $n$ 之和不超过 $200,000$。

输出格式

输出应包含 $t$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个测试用例中有趣的区间数量。

样例

输入 1

2
3
2 1 3
5
3 4 2 5 1

输出 1

2
2

说明

在第一个测试用例中，有趣的区间是 $[2, 2]$（因为 $1 = 1^2$）和 $[2, 3]$（因为 $1 + 3 = 2^2$）。

在第二个测试用例中，有趣的区间是 $[1, 3]$（因为 $3 + 4 + 2 = 3^2$）和 $[5, 5]$（因为 $1 = 1^2$）。