Shuffle

Time Limit: 1 Second Memory Limit: 32768 KB

You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays the songs in that order until all songs have been played. Then it reshuffles and starts playing the list again.

You have a history of the songs that have been played. However, your record of the history of played songs is not complete, as you started recording songs at a certain point in time and a number of songs might already have been played. From this history, you want to know at how many different points in the future the next reshuffle might occur.

A potential future reshuffle position is valid if it divides the recorded history into intervals of length s (the number of songs in the playlist) with the first and last interval possibly containing less than s songs and no interval contains a specific song more than once.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with two integers s and n (1 <= s, n <= 100 000): the number of different songs in the playlist and the number of songs in the recorded playlist history.
One line with n space separated integers, x1, x2, . . . , xn (1 <= xi <= s): the recorded playlist history.

Output

Per testcase:

One line with the number of future positions the next reshuffle can be at. If the history could not be generated by the above mentioned algorithm, output 0.

Sample 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

Sample Output

Submit

Source: Northwestern European 2008