如果一个序列 $b_1, b_2, \dots, b_n$ 满足存在一个 $i$ ($1 \le i \le n$)，使得对于所有 $j$ ($1 \le j < i$) 都有 $b_{j+1} = b_j + d_1$，且对于所有 $j$ ($i \le j < n$) 都有 $b_{j+1} = b_j + d_2$，则称该序列为 $(d_1, d_2)$-等差序列。

Mai 老师有一个序列 $a_1, a_2, \dots, a_n$。他想知道有多少个区间 $[l, r]$ ($1 \le l \le r \le n$) 满足子序列 $a_l, a_{l+1}, \dots, a_r$ 是 $(d_1, d_2)$-等差序列。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 15$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n, d_1, d_2$ ($1 \le n \le 10^5, |d_1|, |d_2| \le 1000$)，下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^9$)。

输出格式

对于每个测试用例，输出答案。

样例

样例输入 1

2
5 2 -2
0 2 0 -2 0
5 2 3
2 3 3 3 3

样例输出 1

12
5