CSCARE-solution

#include<bits/stdc++.h>
using namespace std;

typedef long long   ll;
const ll mod = 1e9 + 7;

#define speedup_IO      ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn(i,a,n)     for(ll i = a; i < n; i++)
#define ford(i,n,a)     for(ll i = n-1; i >= a; i--)
#define pb              push_back
#define lb              lower_bound
#define ub              upper_bound
#define pll             pair<ll,ll>
#define all(a)          (a).begin(),(a).end()
#define reset(a,x)      memset(a,x,sizeof(a))

ll mypow(ll base, ll exp) {ll res = 1; while (exp) {if (exp & 1) res = (res * base) % mod; exp >>= 1, base = (base * base) % mod;} return res;}
ll gcd(ll a, ll b)  { return b ? gcd(b, a % b) : a;            }
ll mult(ll a, ll b) { if (a < 0) {a += mod;} if (b < 0) {b += mod;} return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b)  { if (a < 0) {a += mod;} if (b < 0) {b += mod;} return (a % mod + b % mod) % mod;        }
ll sub(ll a, ll b)  { if (a < 0) {a += mod;} if (b < 0) {b += mod;} return (a % mod + mod - b % mod) % mod;  }

#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << " | ";
	err(++it, args...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 1e18;
const int nax = 1e5 + 5;

vector<int> prefix_function(vector<int> &str)
{
	int n = str.size();
	vector<int>pi(n);

	for (int i = 1; i < n; i++)
	{
		int j = pi[i - 1];
		while (j > 0 && str[j] != str[i])
			j = pi[j - 1];
		if (str[i] == str[j])
			j++;
		pi[i] = j;
	}

	return pi;
}

int count_subarrays(vector<int> &password, vector<int> &entered, int faultiness)
{
	vector<int>pat;
	int n = password.size(), m = entered.size();
	for (int i = 1; i < n; i++)
	{
		pat.pb(password[i] - password[i - 1]);
	}

	pat.pb(1e9);

	for (int i = 1; i < m; i++)
	{
		pat.pb(entered[i] - entered[i - 1]);
	}

	vector<int>pi = prefix_function(pat);

	int ans = 0;
	for (int i = 2 * (n - 1) ; i <= min(m + 2 * (n - 1) - 1, n + m - 2); i++)
	{
		if (pi[i] == n - 1 && abs(password[0] - entered[i - (2 * (n - 1))]) <= faultiness)
		{
			ans++;
		}
	}

	return ans;
}

int main()
{
	int t = 1;
	cin >> t;
	while (t--)
	{
		int faultiness, n, m;
		cin >> faultiness;

		cin >> n;
		vector<int> password(n);
		for (int i = 0; i < n; i++)
		{
			cin >> password[i];
		}

		cin >> m;
		vector<int> entered(m);
		for (int i = 0; i < m; i++)
		{
			cin >> entered[i];
		}

		cout << count_subarrays(password, entered, faultiness) << endl;

	}
	return 0;
}