序列匹配

题目描述

我们都知道，对于两个串 $S$ 与 $T$，我们称 $T$ 在 $S$ 中匹配，当且仅当对于 $S$ 中存在一段序列 $[l,r]$，满足 $\forall_{l \le i \le r} \ S[i] = T[i - l + 1]$。

Orange现在想把匹配推广到一个整数序列，Orange定义序列 $b_i$ 在 序列 $a_i$ 匹配，满足 $\forall_{l \le i \le j \le r} \ a[i] + b[i - l + 1] \equiv a[j] + b[j - l + 1] \pmod k$。记 $a'$ 表示 $a[l\sim r]$，$m$ 表示序列 $b_i$ 的长度，则上述式子可以表示为： $(a'_1 + b_1) \bmod k = (a'_2 + b_2) \bmod k = ... = (a'_m + b_m) \bmod k$。

现在，Orange想知道，$b_i$ 可以在 $a_i$ 中匹配多少个位置？

输入格式

输入包含多组测试数据： 第一行为一个整数 $T$，表示测试数据组数。 对于每组数据： 第一行三个整数，$n, m, k$。 第一行输入 $n$ 个数, 表示序列 $a_i$。 第二行输入 $m$ 个数, 表示序列 $b_i$。

数据范围

$1 \le T \le 15$ $2 \le m \le n \le 2 \times 10^5$ $a_i,b_i \le 10^9$

输出格式

输出一个整数，表示答案。

样例 #1

样例输入 #1

2
3 2 5
7 8 7
8 7
3 2 5
7 8 9
8 7

样例输出 #1

1
2