设有一个包含互不相同的正整数的集合。为了尽可能多地扩展该集合以包含更多整数，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$。请帮助他计算满足 $1 \le l \le r \le n$ 且子数组 $a_l, a_{l+1}, \dots, a_r$ 是辉煌的的整数对 $(l, 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$。

输出格式

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

样例

输入 1

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

输出 1

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]$ 是辉煌的。