Sequence I

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

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$.

Input

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)$.

Output

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.

Sample Input

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

Sample Output

Case #1: 2 Case #2: 1

Hint

wange2014

Source

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

提交代码