Shuffle

Jugyeong loves listening to music, and when she does she uses the shuffle feature of her music player. The player generates a random permutation of the songs in the playlist and plays every song in that order; once all songs have been played, it creates a new permutation (another shuffle) and keeps playing.

Jugyeong has a record of the songs that have been played so far. However, she realized that the record does not begin at the very first song that was ever played. In other words, the record is a contiguous segment that starts at some moment after playback began and ends at some later moment.

Let $s$ be the number of songs in the playlist. The record can be split into consecutive blocks of length $s$, where only the first and the last block may be shorter than $s$ (they correspond to the tail and the head of a shuffle, respectively). Because each block is part of a single permutation produced by one shuffle, no song may appear more than once within the same block.

Such a way of splitting the record is fixed by the position of the first block boundary, which is a single value from $0$ to $s-1$. Count the number of ways to split the record so that every block satisfies the condition. This count is exactly the number of possibilities for how the next shuffle could continue.

The first line contains the number of test cases $T$. $T$ is at most $100$.

For each test case, the first line contains two integers $s$ and $n$ ($1 \le s, n \le 100000$). $s$ is the number of songs in the playlist, and $n$ is the number of songs recorded so far.

The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ separated by spaces, describing the songs that were played ($1 \le x_i \le s$).

For each test case, print on a single line the number of ways to split the record into valid blocks (the number of possible positions for the first block boundary). If no valid split exists, print $0$.