C. Squares in the Notebook
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Juan's notebook has horizontal lines. On a page, it has $$$m$$$ horizontal lines, each separated by one centimeter from the previous one. However, Juan prefers notebooks with a grid pattern. Therefore, he has drawn $$$n$$$ vertical lines on a page of his notebook at the horizontal coordinates $$$a_1, a_2, \ldots, a_n$$$, meaning that the distance from the $$$i$$$-th line to the left edge of the page is $$$a_i$$$ centimeters. Both the horizontal lines and the lines drawn by Juan extend across the entire page.

Now Juan wonders how many squares can be formed with vertices at the intersections of the lines in the notebook. Help Juan count the number of squares.

Input

The first line of the input contains an integer $$$T$$$, the number of cases.

The first line of each case contains two integers $$$m$$$ and $$$n$$$. The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

Output

For each case, print a line with the number of squares.

Scoring

$$$1 \leq T \leq 30$$$.

$$$2 \leq m \leq 10^6$$$.

$$$2 \leq n \leq 10^6$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^6$$$.

$$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 10^9$$$.

26 points: $$$n, m, a_n \leq 100$$$. The sum of $$$n$$$ for all cases is less than $$$500$$$.

16 points: $$$n \leq 2000$$$. The sum of $$$n$$$ for all cases is less than $$$7000$$$.

11 points: $$$m = 2$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^5$$$.

18 points: $$$a_i = i$$$ for $$$1 \leq i \leq n$$$, the sum of $$$n$$$ for all cases is less than $$$2 \cdot 10^5$$$.

29 points: No additional restrictions.

Example
Input
3
4 3
1 3 4
3 2
1 5
2 2
1 2
Output
6
0
1