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.