Carol 有一个长度为 n 的数组 a，他定义函数 f(l,r)=\sum_{i=l}^{r-1}(a_i-a_{i+1})，其中 1\leq l\leq r\leq n，特殊地，f(i,i) 定义为 0。

如果 f(l,r)\neq (a_r-a_l)，则称一个子区间 [l,r](1\leq l\leq r\leq n) 是不稳定的。

Carol 想知道数组 a 有多少个不稳定的子数组。

第一行一个整数 T 表示数据组数，对于每组数据：

第一行一个整数 n 表示数组长度。

第二行 n 个整数 a_1,a_2,\dots,a_n 表示数组 a。

对于每组数据，输出一行一个整数表示答案。

对于 30\% 的数据，\sum n\leq 1000，0\leq a_i\leq 1。

对于 60\% 的数据，\sum n\leq 10^5，0\leq a_i\leq 1。

对于 100\% 的数据，1\leq T\leq 10^5，n\ge 1，\sum n\leq 10^5，0\leq a_i\leq 10^9。