时间限制：1秒　　内存限制：256M

---

【题目描述】

　　你正在使用的音乐播放器有个所谓的乱序功能，即随机打乱歌曲的播放顺序。
　　假设一共有 \(n\) 首歌曲，则一开始会给这 \(n\) 首歌随机排序（我们称为一轮播放），全部播放完毕后再重新随机排序、继续播放（新的一轮），依次类推。注意，当 \(n\) 首歌播放完毕之前不会重新排序。这样，播放记录里的每 \(n\) 首歌都是 \(1..n\) 的一个排列。

　　现在给出一个长度为 \(m\) 的播放记录：\(x[1],x[2],…,x[m](1≤x[i]≤n)\)，注意：这个记录不一定是从某轮的最开始记录的。你的任务是统计下一轮的开始位置有多少种可能性(上一轮的记录可能不全，但不能为空)。

　　例如，\(n=4\)，播放记录是：3,4,4,1,3,2,1,2,3,4，不难发现只有一种可能性：前两首是一个段的最后两首歌，因此答案是1；当 \(n=3\) 时，播放记录：1,2,1，有两种可能：第一首是一段，后两首是另一段；前两首是一段，最后一首是另一段。答案是2。

【输入格式】

　　第一行是整数 \(T\)，表示测试数据个数。
　　每组测试数据包含两行，第一行是 \(n,m\)，表示歌曲数目和播放记录序列的长度。第二行是 \(m\) 个整数 \(x_1,x_2,…,x_m（1 ≤x_i≤n）\)，表示播放记录。

【输出格式】

　　每个测试数据输出一行，一个整数，表示答案。如果不能找到合适的答案，则输出 0。

【输入输出样例】

　Input

4
4 10
3 4 4 1 3 2 1 2 3 4
6 6
6 5 4 3 2 1
3 5
3 3 1 1 1
7 3
5 7 3

　Output

1
6
0
7

【数据限制】

　　\(100\%\) 的数据满足，\(1 ≤ m ,n ≤ 100000\)。

【来源】

　　Mr.he