Monocarp has installed a new fence at his summer house. The fence consists of $$$n$$$ planks of the same size arranged in a row.

Monocarp decided that he would paint his fence according to the following rules:

each plank of the fence will be painted in exactly one color;
the number of different colors that the planks will be painted in is exactly two;
the planks of the fence that are painted in the same color must form a continuous sequence, meaning that for all pairs of planks painted in the same color, there will be no planks painted in a different color between them.

Monocarp has $$$m$$$ different paints, and the paint of the $$$i$$$-th color is sufficient to paint no more than $$$a_i$$$ planks of the fence. Monocarp will not buy any additional paints.

Your task is to determine the number of different ways to paint the fence that satisfy all of Monocarp's described wishes. Two ways to paint are considered different if there exists a plank that is painted in different colors in these two ways.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — the number of planks in the fence and the number of different colors of paint that Monocarp has.

The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the maximum number of planks that can be painted with the paint of color $$$i$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. The sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the number of different ways to paint the fence that satisfy all of Monocarp's described wishes.

Note

In the first test case, there are $$$4$$$ different ways to paint the fence (the sequences of color numbers in which the planks can be painted from left to right are listed below):

$$$[1, 2, 2, 2, 2]$$$;
$$$[1, 1, 2, 2, 2]$$$;
$$$[2, 2, 2, 1, 1]$$$;
$$$[2, 2, 2, 2, 1]$$$.

In the second test case, there are $$$6$$$ different ways to paint the fence (the sequences of color numbers in which the planks can be painted from left to right are listed below):

$$$[1, 2, 2, 2, 2]$$$;
$$$[1, 1, 2, 2, 2]$$$;
$$$[1, 1, 1, 2, 2]$$$;
$$$[2, 2, 1, 1, 1]$$$;
$$$[2, 2, 2, 1, 1]$$$;
$$$[2, 2, 2, 2, 1]$$$.

Idx	Name	Rating
A	To Zero	800
B	Array Recoloring	1300
C	Two Colors	1500
D	Equalization	2000
E	XOR Matrix	2500
F	Beautiful Sequence Returns	3000

Educational Codeforces Round 176 (Rated for Div. 2)