C. Eri 与扩展集合

时间限制：3 秒
内存限制：512 MB

考虑一个包含互不相同正整数的集合。为了扩展集合使其包含尽可能多的整数，Eri 可以选择集合中两个不同的整数 $x \neq y$，使得它们的平均数 $\frac{x+y}{2}$ 仍然是正整数且不在集合中，然后将它加入集合。原有的 $x$ 和 $y$ 仍保留在集合中。

如果集合中的元素排序后，任意相邻元素的差为 $1$，则称该集合是连续的。例如，集合 $\{2\}$、$\{2,5,4,3\}$、$\{5,6,8,7\}$ 是连续的，而 $\{2,4,5,6\}$、$\{9,7\}$ 不是。

Eri 喜欢连续集合。假设有一个数组 $b$，Eri 将 $b$ 中的所有元素放入集合（重复元素只放入一次）。如果在有限次上述操作后，集合能变成连续的，则称数组 $b$ 是精彩的。

Eri 有一个长度为 $n$ 的正整数数组 $a$。请帮助他统计有多少对整数 $(l, r)$（$1 \le l \le r \le n$），使得子数组 $a_l, a_{l+1}, \dots, a_r$ 是精彩的。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 4 \cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$ 的元素。

数据保证：所有测试用例的 $n$ 之和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 精彩子数组的数量。

示例

输入

6
2
2 2
6
1 3 6 10 15 21
5
6 30 18 36 9
1
1000000000
6
1 1 4 5 1 4
12
70 130 90 90 90 108 612 500 451 171 193 193

输出

3
18
5
1
18
53

样例解释

第一个测试用例：数组 $a = [2,2]$ 有 3 个子数组：$[2]$、$[2]$ 和 $[2,2]$。每个子数组的集合都只包含一个整数 $2$，因此总是连续的。所有这些子数组都是精彩的，所以答案是 $3$。

第二个测试用例：考虑子数组 $[3,6,10]$。可以按如下方式操作：

$\{3,6,10\} \xrightarrow{x=6,y=10} \{3,6,8,10\} \xrightarrow{x=6,y=8} \{3,6,7,8,10\} \xrightarrow{x=3,y=7} \{3,5,6,7,8,10\}$
$\xrightarrow{x=3,y=5} \{3,4,5,6,7,8,10\} \xrightarrow{x=8,y=10} \{3,4,5,6,7,8,9,10\}$

$\{3,4,5,6,7,8,9,10\}$ 是连续集合，所以子数组 $[3,6,10]$ 是精彩的。