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 rst and last interval possibly containing less than s

songs and no interval contains a specic song more than once.

Input

On the rst 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 ≤ 100000): 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

1

6

0

7

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <ctime>

 #include <set>

 #define time_ printf("time = %f\n",double(clock())/CLOCKS_PER_SEC)

 using namespace std;

 const int maxn=;

 int s,n;

 int seq[maxn+];

 int num[maxn+];

 int id[maxn+];

 void pre_process(){

     int l=,r=;

     memset(num,,sizeof num);

     memset(id,,sizeof id);

     int single=;

     for(;r<l+s&&r<n;r++){

         int id=seq[r];

         num[id]++;

         if(num[id]==) single++;

         else single--;

     }

     if(single==r-l) id[l]=;

     while(l<n){

         int a=seq[l];

         int b=seq[r];

         num[a]--;

         if(num[a]==) single--;

         if(num[a]==) single++;

         l++;

         if(r!=n){

             num[b]++;

             if(num[b]==) single++;

             if(num[b]==) single--;

             r++;

         }

         if(l!=n&&single==r-l) id[l]=;

     }

 }

 int main(int argc, const char * argv[]) {

     int T;

     scanf("%d",&T);

     while(T--){

         scanf("%d%d",&s,&n);

         for(int i=;i<n;i++)

             scanf("%d",&seq[i]);

         pre_process();

         int ans=;

         int rst[maxn+];

         memset(rst,,sizeof rst);

         rst[seq[]]++;

         int single=;

         for(int d=;d<=s&&d<=n;d++){

             bool ok=true;

             if(single!=d) break;;

             for(int pt=d;pt<n;pt+=s){

                 if(id[pt]==){

                     ok=false;

                     break;

                 }

             }

             if(ok) ans++;

             rst[seq[d]]++;

             if(rst[seq[d]]==) single++;

         }

         if(n<s&&ans==n)

             ans=s;

         printf("%d\n",ans);

     }

     return ;

 }