1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int maxn = 5000000; 6  7 int t;  8  9 int s,n;10 11 int a[maxn+10];12 13 int res[maxn+10];14 15 int flag[maxn+10];16 17 void init(){18     memset(a, 0, sizeof(a));19     memset(res, 0, sizeof(res));20     memset(flag, 0, sizeof(flag));21 }22 23 24 25 int main(){26 //freopen("a.txt", "w", stdout);27     scanf("%d",&t);28     while(t--){29         init();30         scanf("%d%d",&s, &n);31         for(int i = 1; i <= n; ++i){32             scanf("%d",&a[i]);33         }34         for(int i = 1; i <= s; ++i){35             a[i+n] = i + maxn/10;36         }37 38         int temp = s;39         for(int i = 1; i <= n+s-1; ++i){40                 if(i <= s){41                     42                     temp -= 1;43                     flag[a[i]] += 1;44                     45                     if(flag[a[i]] == 1){46                         temp += 1;47                     } else if(flag[a[i]] == 2){48                         temp -= 1;49                     }50                     if(temp == s){51                 52                         res[i] = 1;53                     }54                 } else {55                     56                     flag[a[i-s]] -= 1;57                     58                     if(flag[a[i-s]] == 0){59                         temp -= 1;60                     } else if(flag[a[i-s]] == 1){61                         temp += 1;62                     }63                     64                     flag[a[i]] += 1;65                     if(flag[a[i]] == 1){66                         temp += 1;67                     } else if(flag[a[i]] == 2){68                         temp -= 1;69                     }70                     71                     if(temp == s){72                         73                         res[i%s] = res[i%s]&1;74                     } else {75                         res[i%s] = 0;76                     }77                 } 78         }79 80         int ans = 0;81         if(n <= s && res[n] == 1){82             ans = s;83         } else {84         for(int i = 1; i <= s; ++i){85                 if(res[i] == 1){86                     ++ans;87                 }88         }89     }90         printf("%d\n",ans);91 92     }93 }