Anmol gained a lot of weight last semester. So this semester, he decided to run everyday. There is a very long straight road starting at his hostel. There are N poles on the road - P1, P2, P3,..., PN on the road. All the poles lie on the same side of his hostel. The distance between Pi and his hostel is Di.
For 1 ≤ i, j ≤ N, i < j implies Di < Dj
Everyday, Anmol chooses a pole Pi to start running from. He keeps on running until he reaches Pi+K. Whenever he reaches a pole (other than the starting pole), he records the distance traveled since the last pole.

You are given the distances recorded by him today. Your task is to find the number of distinct values of i such that i + K ≤ N and if he starts at Pi and end at Pi+K, he would end up having exactly the same record of distances (in the same order).

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains two space separated integers N and K.
- The next line contains N space separated integers D1, D2,..., DN.
- The next line contains K space separated integers representing the distances recorded by Anmol in the same order.
.

-----Output-----
- For each test case, output a single line containing the answer for that test case.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 5 x 104
- 1 ≤ K < N
- 1 ≤ Di ≤ 106

-----Subtasks-----

-----Subtask #1 (20 points)-----
- 1 ≤ N ≤ 1000

-----Subtask #2 (80 points)-----
- Original constraints

-----Example-----
Input:
3
5 1
1 5 10 12 14
5
5 2
5 8 13 16 21
3 5
5 3
2 6 8 11 16
2 3 5

Output:
1
2
1

-----Explanation-----
Example case 1. If he runs from P2 to P3, he will record (5)
Example case 2. He can start at P1 or P3
Example case 3. He can start at P2

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '#code snippet reference:http://www.geeksforgeeks.org/searching-for-patterns-set\xa0\xa0\xa0\xa0-2-kmp-algorithm/\ndef KMPMatch(pattern, string):\n M = len(pattern)\n N = len(string)\n nonlocal ans\n\n lps = [0]*M\n j = 0 \n LPSCompute(pattern, M, lps)\n\n i = 0 \n while i < N:\n  if pattern[j] == string[i]:\n   i+=1\n   j+=1\n\n  if j==M:\n   ans+=1\n   j = lps[j-1]\n   \n  elif i < N and pattern[j] != string[i]:\n   if j != 0:\n    j = lps[j-1]\n   else:\n    i+=1\n\ndef LPSCompute(pattern, M, lps):\n len = 0 \n lps[0] \n i = 1\n while i < M:\n  if pattern[i]==pattern[len]:\n   len+=1\n   lps[i] = len\n   i+=1\n  else:\n   if len!=0:\n    len = lps[len-1]\n\n   else:\n    lps[i] = 0\n    i+=1\n\nfor _ in range(int(input())):\n n,k=list(map(int,input().split()))\n s=list(map(int,input().split()))\n pattern=list(map(int,input().split()))\n ans=0\n string=[]\n for i in range(n-1):\n  string.append(s[i+1]-s[i])\n KMPMatch(pattern, string)\n print(ans)\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: