Schtiffles - Marbl⠀

James is learning numbers, and he is having fun writing them on a huge blackboard, from left to right.

• At the beginning, James writes the number $1$.
• Right after, James writes $1$ again, and then $2$.
• Then James writes $1$, $2$, $3$.
• $\ldots$
• In the end, James writes $1$, $2$, $3$, $\ldots$, $n$.

For example, for $n = 5$, the numbers written by James make the array $b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$.

James has a list of favorite numbers $a_1, a_2, \ldots, a_m$, and he wants to calculate how many subarrays of the array $b$ are equal to $a_1, a_2, \ldots, a_m$. $^{\text{∗}}$

James is already sure that $a_1, a_2, \ldots, a_m$ is a subarray of $b$, so the answer is at least $1$.

$^{\text{∗}}$The subarrays of an array $[v_1, v_2, \ldots, v_k]$ are generated as follows: for each $l, r$ such that $1 \leq l \leq r \leq k$, the array $[v_l, v_{l+1}, \ldots, v_r]$ is a subarray. So there are $k(k+1)/2$ subarrays in total, and some of them may be equal.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 200$) — the maximum number written by James, and the length of the array $a_1, a_2, \ldots, a_m$.

The second line of each test case contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \leq a_i \leq 10^5$) — James' favorite numbers.

It is guaranteed that for the given input, the answer is always at least $1$.

Note that there are no constraints on the sum of $n$ and $m$ over all test cases.

Output

For each test case, output a single line containing an integer: the number of subarrays of the array $b$ which are equal to $a_1, a_2, \ldots, a_m$.

Note

In the first test case, the blackboard contains the numbers

$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$</p><p>and James has only one favorite number: the number$1$. There are$4$subarrays of$b$equal to$[1]$(highlighted in red):</p><ul> <li>$[\color{red}{1}, 1, 2, 1, 2, 3, 1, 2, 3, 4]$; </li><li>$[1, \color{red}{1}, 2, 1, 2, 3, 1, 2, 3, 4]$; </li><li>$[1, 1, 2, \color{red}{1}, 2, 3, 1, 2, 3, 4]$; </li><li>$[1, 1, 2, 1, 2, 3, \color{red}{1}, 2, 3, 4]$. </li></ul><p>In the second test case, the blackboard contains the numbers</p><p>$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$</p><p>and James's list of favorite numbers is$[1, 2, 3]$. There are$3$subarrays of$b$equal to$[1, 2, 3]$(highlighted in red):</p><ul> <li>$[1, 1, 2, \color{red}{1, 2, 3}, 1, 2, 3, 4, 1, 2, 3, 4, 5]$; </li><li>$[1, 1, 2, 1, 2, 3, \color{red}{1, 2, 3}, 4, 1, 2, 3, 4, 5]$; </li><li>$[1, 1, 2, 1, 2, 3, 1, 2, 3, 4, \color{red}{1, 2, 3}, 4, 5]$. </li></ul><p>In the third test case, the blackboard contains the numbers</p><p>$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$</p><p>and James's list of favorite numbers is$[3, 1, 2, 3, 4, 1]$. There is only$1$subarray of$b$equal to$[3, 1, 2, 3, 4, 1]$(highlighted in red):</p><ul> <li>$[1, 1, 2, 1, 2, \color{red}{3, 1, 2, 3, 4, 1}, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$. ## Samples ```input1 5 4 1 1 5 3 1 2 3 6 6 3 1 2 3 4 1 100000 1 100000 4 2 1 1 ``` ```output1 4 3 1 1 1 ```$$