你正在使用随机播放（shuffle）功能听你的音乐收藏，以保持音乐的惊喜感。你假设音乐播放器的随机播放算法会生成播放列表中所有歌曲的一个随机排列，并按该顺序播放，直到所有歌曲都播放完毕。然后，它会重新洗牌（reshuffle）并再次开始播放该列表。

你记录了一份已播放歌曲的历史记录。然而，你的记录并不完整，因为你是在某个时间点才开始记录的，此时可能已经播放了一些歌曲。根据这份历史记录，你想知道未来的下一次重新洗牌可能会在多少个不同的时间点发生。

如果一个潜在的未来重新洗牌位置能够将记录的历史分割成长度为 $s$（播放列表中的歌曲数量）的区间，且第一个和最后一个区间可能包含少于 $s$ 首歌曲，并且没有任何一个区间多次包含同一首歌曲，则该位置是合法的。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。

对于每个测试用例：

• 第一行包含两个整数 $s$ 和 $n$ ($1 \le s, n \le 100\,000$)：播放列表中不同歌曲的数量，以及记录的播放历史中的歌曲数量。
• 第二行包含 $n$ 个空格分隔的整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le s$)：记录的播放历史。

输出格式

对于每个测试用例：

• 输出一行，包含下一次重新洗牌可能发生的未来位置的数量。如果该历史记录不可能由上述算法生成，则输出 0。

样例

输入 1

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

输出 1

1
6
0
7