看注释
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
void solve()
{
int n,m,k;
cin>>n>>m>>k;
//将式子做个变换,有(a[i] - a[i-1]) % k == (b[i] - b[i-1]) %k
vector<int> a(n+1), b(m+1);
for(int i = 1; i <= n; ++i) cin>>a[i], a[i] %= k;
for(int i = 1; i <= m; ++i) cin>>b[i], b[i] %= k;
vector<int> s(n), t(m);
for(int i = 1; i < n; ++i) s[i] = (a[i + 1] - a[i] + k) % k;
for(int i = 1; i < m; ++i) t[i] = (b[i] - b[i + 1] + k) % k;
n --, m --;
auto KMP = [&](vector<int> &s, vector<int> &t) ->int
{
int cnt = 0;
vector<int> nxt(m + 1);
for (int i = 2, j = 0; i <= m; i++)
{
while (j && t[i] != t[j + 1]) j = nxt[j];
if (t[i] == t[j + 1]) j++;
nxt[i] = j;
}
for (int i = 1, j = 0; i <= n; i++)
{
while (j && s[i] != t[j + 1]) j = nxt[j];
if (s[i] == t[j + 1]) j++;
if (j == m)
{
//cout << i - m + 1 << "\n"; // t 在 s 中出现的位置
j = nxt[j];
cnt ++;
}
}
return cnt;
//for(int i = 1; i <= m; ++i) cout<<nxt[i]<<' ';
};
cout<<KMP(s, t)<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}