311154: CF1942C1. Bessie's Birthday Cake (Easy Version)

C1. Bessie's Birthday Cake (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputProof Geometric Construction Can Solve All Love Affairs - manbo-p⠀

This is the easy version of the problem. The only difference between the two versions is the constraint on $y$. In this version $y = 0$. You can make hacks only if both versions are solved.

Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $n$ sides. The vertices of the cake are numbered from $1$ to $n$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices.

Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted).

Bessie has already chosen $x$ of those vertices that can be used to form diagonals. She wants you to choose no more than $y$ other vertices such that the number of triangular pieces of cake she can give out is maximized.

What is the maximum number of triangular pieces of cake Bessie can give out?

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case consists of three integers, $n$, $x$, and $y$ ($4 \leq n \leq 10^9$, $2 \leq x \leq \min(n, 2 \cdot 10^5)$, $y = 0$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose.

The second line consists of $x$ distinct integers from $1$ to $n$, representing the vertices Bessie has chosen.

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

Output

For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out.

ExampleInput

3
8 4 0
1 6 2 5
8 8 0
1 3 2 5 4 6 7 8
4 2 0
1 3

Output

2
6
2

Note

In test cases $1$, $2$ and $3$, you can get $2$, $6$ and $2$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures:

The green dots represent vertices that can be used, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted.

题目大意：
这是一个关于选择多边形顶点以最大化分割成三角形数量的题目。给定一个有n个边的正多边形，其顶点编号为1到n。已经选择了x个顶点来形成非交叉的对角线，你需要选择不超过y个其他顶点（在这个简单版本中y=0），以使得可以给出的三角形状蛋糕块的数量最大化。要求输出的是可以给出的三角形状蛋糕块的最大数量。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
每个测试用例的第一行包含三个整数n、x和y（4≤n≤10^9，2≤x≤min(n, 2×10^5)，y=0），分别表示多边形的边数、Bessie已经选择的顶点数和你可以选择的其他顶点的最大数量。
每个测试用例的第二行包含x个从1到n的不同的整数，表示Bessie已经选择的顶点。
保证所有测试用例中x的总和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数，表示可以给出的三角形状蛋糕块的最大数量。

例：
输入：
3
8 4 0
1 6 2 5
8 8 0
1 3 2 5 4 6 7 8
4 2 0
1 3

输出：
2
6
2

注意：
在测试用例1、2和3中，分别可以得到2、6和2个非交叉的三角形状蛋糕块。可能的构造如下图所示：
绿色的点表示可以使用的顶点，蓝色的线表示画出的对角线，红色的数字表示被计数的三角形。题目大意： 这是一个关于选择多边形顶点以最大化分割成三角形数量的题目。给定一个有n个边的正多边形，其顶点编号为1到n。已经选择了x个顶点来形成非交叉的对角线，你需要选择不超过y个其他顶点（在这个简单版本中y=0），以使得可以给出的三角形状蛋糕块的数量最大化。要求输出的是可以给出的三角形状蛋糕块的最大数量。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 每个测试用例的第一行包含三个整数n、x和y（4≤n≤10^9，2≤x≤min(n, 2×10^5)，y=0），分别表示多边形的边数、Bessie已经选择的顶点数和你可以选择的其他顶点的最大数量。 每个测试用例的第二行包含x个从1到n的不同的整数，表示Bessie已经选择的顶点。 保证所有测试用例中x的总和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数，表示可以给出的三角形状蛋糕块的最大数量。 例： 输入： 3 8 4 0 1 6 2 5 8 8 0 1 3 2 5 4 6 7 8 4 2 0 1 3 输出： 2 6 2 注意： 在测试用例1、2和3中，分别可以得到2、6和2个非交叉的三角形状蛋糕块。可能的构造如下图所示： 绿色的点表示可以使用的顶点，蓝色的线表示画出的对角线，红色的数字表示被计数的三角形。