Sequence I

Mr. Frog has two sequences $a_1,a_2,\cdots ,a_n$ and $b_1,b_2,\cdots ,b_m$ and a number p. He wants to know the number of positions q such that sequence $b_1,b_2,\cdots ,b_m$ is exactly the sequence $a_q,a_{q+p},a_{q+2p},\cdots ,a_{q+(m-1)p}$ where $q + (m - 1)p\leq n$ and $q\geq 1$.

The first line contains only one integer $T\leq 100$, which indicates the number of test cases.

Each test case contains three lines.

The first line contains three space-separated integers $1\leq n\leq 10^6, 1\leq m\leq 10^6$ and $1\leq p\leq 10^6$.

The second line contains n integers $a_1,a_2,\cdots ,a_n(1 \leq a_i \leq 10^9)$.

the third line contains m integers $b_1,b_2,\cdots ,b_m(1 \leq b_i \leq 10^9)$.

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of valid q’s.

2
6 3 1
1 2 3 1 2 3
1 2 3
6 3 2
1 3 2 2 3 1
1 2 3

Case #1: 2
Case #2: 1

2016中国大学生程序设计竞赛（长春）-重现赛