题目内容

机房温感阵列回传了一条长度为 $n$ 的整型读数序列 $v_1,v_2,\ldots,v_n$。巡检侧需要统计：有多少个非空连续窗口，其读数之和恰好等于窗口长度的平方。

具体地，对任意 $1\le L\le R\le n$，记窗口长度为 $\ell=R-L+1$，窗口和为

若该和等于 $\ell^2$，则计为一个合法窗口。请对每个询问给出合法窗口个数。

输入描述

第一行一个整数 $q$（$1\le q\le 10^5$），表示询问个数。

每个询问：

• 第一行一个整数 $n$（$1\le n\le 10^5$）；
• 第二行 $n$ 个整数 $v_1,v_2,\ldots,v_n$（$|v_i|\le 100$）。

保证单个文件中所有询问的 $n$ 之和不超过 $2\cdot 10^5$。

输出描述

对每个询问输出一行一个非负整数，表示合法窗口个数。

样例1

输入

1
3
1 3 1

输出

4

说明

长度 $1$ 要求单点读数为 $1$，下标 $1$ 与 $3$ 各贡献 $1$。长度 $2$ 要求和为 $4$，窗口 $[1,2]$ 与 $[2,3]$ 的和均为 $4$。长度 $3$ 要求和为 $9$，整段和为 $5$，不成立。合计 $4$。

样例2

输入

2
3
2 0 2
3
-2 1 1

输出

0
2

说明

第 $1$ 个询问：各长度要求分别为 $1,4,9$，实际各子段和均对不上，答案 $0$。

第 $2$ 个询问：两个单点 $1$ 满足长度 $1$；其余长度均不满足，答案 $2$。