Without Any Legend
You have two arrays $A_1, A_2, ..., A_N$ and $C_1, C_2, ..., C_N$ of length $N$. Initially for each integer $i$ $(1 \leq i \leq N)$, $C_i = A_i$.
Now, you are given another array $B_1, B_2, ..., B_M$ of length $M$ and you are asked to count the number of segments in array $C$ where array $B$ completely overlaps. More formally, array $B$ will completely overlap along with a segment of array $C$ if there is a segment $\left[i, j\right]$ in array $C$ where, $\left(j\ –\ i+1\right) = M$ and $C_i = B_1,$ $C_{i+1} = B_2, ...,$ $C_j = B_M$.
Before start counting you can do an operation as many times as you wish to maximize the number of segments where array $B$ completely overlaps. The operation is –
- Choose an integer
$i$$(1 \leq i \leq N)$, then make$C_i = C_i + A_i$.
Input
The first line contains an integer $T$ $\left(1 \leq T \leq 5\right)$ – number of test cases.
Each test case contains four lines.
The first line of each test case contains an integer $N$ $\left(1 \leq N \leq 10^4\right)$.
Next line contains $N$ integers $A_1, A_2, ..., A_N$ $\left(1 \leq A_i \leq 10^6\right)$.
Next line contains an integer $M$ $\left(1 \leq M \leq 100\right)$.
The last line of each test case contains $M$ integers $B_1, B_2, ..., B_M$ $\left(1 \leq B_i \leq 10^6\right)$.
Output
The maximum number of segments in array $C$ where array $B$ completely overlaps.
Sample
| Input | Output |
|---|---|
2 4 2 3 2 3 2 6 6 6 2 3 5 2 5 2 3 10 15 10 | 3 2 |
For 1st test case —
Initially, $C = \left[2, 3, 2, 3\right]$
Choose $i = 1, C_1 = C_1 + A_1 = 2 + 2 = 4$
Choose $i = 1, C_1 = C_1 + A_1 = 4 + 2 = 6$
Choose $i = 4, C_4 = C_4 + A_4 = 3 + 3 = 6$
Choose $i = 3, C_3 = C_3 + A_3 = 2 + 2 = 4$
Choose$ i = 2, C_2 = C_2 + A_2 = 3 + 3 = 6$
Choose $i = 3, C_3 = C_3 + A_3 = 4 + 2 = 6$
After performing the operations, $C = \left[6, 6, 6, 6\right]$.
So, there are three segments $[1, 2], [2, 3]$ and $[3, 4]$ in array $C$ where array $B$ completely
overlaps. No other construction can make more than three segments.
