C. Two Colors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
3
5 2
2 4
5 2
3 4
12 3
5 9 8
Output
4
6
22
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. $$$[1, 2, 2, 2, 2]$$$;
  2. $$$[1, 1, 2, 2, 2]$$$;
  3. $$$[2, 2, 2, 1, 1]$$$;
  4. $$$[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. $$$[1, 2, 2, 2, 2]$$$;
  2. $$$[1, 1, 2, 2, 2]$$$;
  3. $$$[1, 1, 1, 2, 2]$$$;
  4. $$$[2, 2, 1, 1, 1]$$$;
  5. $$$[2, 2, 2, 1, 1]$$$;
  6. $$$[2, 2, 2, 2, 1]$$$.