神性之陨
题号：NC267934
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

唯有神性不存
人智方可显现
白垩色的王子有一张 n 行 m 列的由方格构成的地图，初始时地图上的所有格子都是障碍。白垩色的王子对于每一列给定了一个值 a_i，表示你需要在这一列上选定 a_i 个连续的格子，将这些格子变成通路（保证 a_1=a_m=1）。
每次游戏白垩色的王子会从第 1 列的那个通路格开始行动，他可以向上下左右进行移动。白垩色的王子不能走走过的格子。如果白垩色的王子走到了第 m 列，就视作他完成了游戏。
对于某一些构造方案，该地图存在且仅存在一条路径可以完成游戏，询问对于所有的这些方案，有多少个可能的终点。换言之，记第 m 列的通路格所在的行序号为 b_m，询问 b_m 有多少种可能的取值。

输入描述:

第一行输入一个整数 T(1\le T \le 500)，表示数据组数。
对于每一组数据，第一行输入两个整数 n,m(1 \le n \le \sum n \le 5000,2 \le m \le \sum m \le 5000)，表示地图的行数和列数。
接下来一行，输入 m 个整数，表示 a_1,a_2 \dots a_m(1\le a_i \le n)，保证 a_1=a_m=1。

输出描述:

对于每一组数据，输出一行一个整数，表示使得地图存在且只存在一条路径可以完成游戏的方案中的可能的终点数。若不存在符合条件的构造，输出 0 即可。
示例1

输入

复制 
3
4 4
1 2 2 1
7 5
1 2 5 3 1
3 4
1 3 2 1

输出

复制 
4
6
0

说明

对于第一组数据：每一行都有可能成为终点。

如图，橙黄色部分为可能的终点，即最后一列的格子可以为所有橙黄色格子中的其中一个。

对于第二组数据：除了第四行以外均可行。

如图，橙黄色部分为可能的终点，即最后一列的格子可以为所有橙黄色格子中的其中一个。

对于第三组数据：不存在任何一种方案可行。