311109: CF1935D. Exam in MAC

D. Exam in MACtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The Master's Assistance Center has announced an entrance exam, which consists of the following.

The candidate is given a set $s$ of size $n$ and some strange integer $c$. For this set, it is needed to calculate the number of pairs of integers $(x, y)$ such that $0 \leq x \leq y \leq c$, $x + y$ is not contained in the set $s$, and also $y - x$ is not contained in the set $s$.

Your friend wants to enter the Center. Help him pass the exam!

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $c$ ($1 \leq n \leq 3 \cdot 10^5$, $1 \leq c \leq 10^9$) — the size of the set and the strange integer.

The second line of each test case contains $n$ integers $s_1, s_2, \ldots, s_{n}$ ($0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$) — the elements of the set $s$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output a single integer — the number of suitable pairs of integers.

ExampleInput

8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353

Output

3
16139
10
2
33
36
35
499999998999122959

Note

In the first test case, the following pairs are suitable: $(0, 0)$, $(2, 2)$, $(3, 3)$.

In the third test case, the following pairs are suitable: $(0, 1)$, $(0, 2)$, $(0, 4)$, $(1, 3)$, $(2, 6)$, $(3, 4)$, $(3, 5)$, $(4, 5)$, $(4, 6)$, $(5, 6)$.

题目大意：给定的一个整数集s和整数c，求满足以下条件的整数对(x, y)的对数：0 ≤ x ≤ y ≤ c，且x + y和y - x都不在集合s中。

输入数据格式：
- 第1行：一个整数t（1 ≤ t ≤ 2 × 10^4），表示测试用例的数量。
- 每个测试用例的输入格式：
- 第1行：两个整数n和c（1 ≤ n ≤ 3 × 10^5，1 ≤ c ≤ 10^9），分别表示集合s的大小和整数c。
- 第2行：n个整数s_1, s_2, ..., s_n（0 ≤ s_1 < s_2 < ... < s_n ≤ c），表示集合s的元素。

输出数据格式：
- 对于每个测试用例，输出一个整数，表示满足条件的整数对(x, y)的对数。

示例：
输入：
```
8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353
```
输出：
```
3
16139
10
2
33
36
35
499999998999122959
```题目大意：给定的一个整数集s和整数c，求满足以下条件的整数对(x, y)的对数：0 ≤ x ≤ y ≤ c，且x + y和y - x都不在集合s中。 输入数据格式： - 第1行：一个整数t（1 ≤ t ≤ 2 × 10^4），表示测试用例的数量。 - 每个测试用例的输入格式： - 第1行：两个整数n和c（1 ≤ n ≤ 3 × 10^5，1 ≤ c ≤ 10^9），分别表示集合s的大小和整数c。 - 第2行：n个整数s_1, s_2, ..., s_n（0 ≤ s_1 < s_2 < ... < s_n ≤ c），表示集合s的元素。 输出数据格式： - 对于每个测试用例，输出一个整数，表示满足条件的整数对(x, y)的对数。 示例： 输入： ``` 8 3 3 1 2 3 1 179 57 4 6 0 3 5 6 1 1 1 5 10 0 2 4 8 10 5 10 1 3 5 7 9 4 10 2 4 6 7 3 1000000000 228 1337 998244353 ``` 输出： ``` 3 16139 10 2 33 36 35 499999998999122959 ```