硕士辅导中心公布了入学考试,考试内容如下。
给候选者一个大小为 $$$n$$$ 的集合 $$$s$$$ 和一些奇怪的整数 $$$c$$$。对于这个集合,需要计算整数对$$$(x, y)$$$的数量,使得$$$0 \leq x \leq y \leq c$$$、$$$x + y$$$不包含在集合$$$s$$$中,并且$$$y - x$$$也不包含在集合$$$s$$$中。
您的朋友想要进入中心。帮助他通过考试!
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — 集合的大小和奇怪的整数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — 集合 $$$s$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 合适的整数对的数量。
示例
输入 #1
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
输出 #1
3 16139 10 2 33 36 35 499999998999122959
注意
在第一个测试用例中,以下对是合适的:$$$(0, 0)$$$、$$$(2, 2)$$$、$$$(3, 3)$$$。
在第三个测试用例中,以下对是合适的: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4、5)$$$、$$$(4、6)$$$、$$$(5、6)$$$。