# Distance

Time Limit: 3 Seconds

Memory Limit: 65536 KB

## Description

We define $\sum |a_i - b_i|^p$ as the distance of two vectors $(a_1, a_2, \dots, a_n)$ and $(b_1, b_2, \dots, b_n)$ where $p$ is a given integer. Only two vectors with the same number of integers have distance between them.

Now please find the number of sub-vector pairs from vector $X = (x_1, x_2, ..., x_n)$ and $Y = (y_1, y_2, ..., y_n)$ respectively, such that the distance between the two sub-vectors is no more than $V$. A sub-vector means a successive part of the referencing vector.

## Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases. There are only about 10 big cases. For each test case:

The first line contains three integers $n$, $V$, and $p$ ($1 \le n \le 10^3$, $0 \le V \le 10^{18}$, $p \in \{1, 2, 3\}$).

The following line contains $n$ non-negative integers $x_1, x_2, \dots, x_n$ ($0 \le x_i^p \le 10^9$), indicating the vector $X$.

The following line contains $n$ non-negative integers $y_1, y_2, \dots, y_n$ ($0 \le y_i^p \le 10^9$), indicating the vector $Y$.

## Output

For each test case output one single line, representing the number of required vector pairs.

## Sample Input

2
5 2 1
1 1 1 1 1
1 1 1 1 1
5 0 2
2 1 3 4 5
5 4 3 2 1

## Sample Output

55
6

## Hint

In sample 1, for sub-vector with length 1, any sub-vector in $X$ is equal to that in $Y$, so there are 25 pairs. For sub-vector with length 2, 3, 4, 5 the number of pairs are 16, 9, 4, 1 respectively. So the answer is 55.

In Sample 2, the six pairs are: (1)(1), (2)(2), (3)(3), (4)(4), (5)(5) and (2, 1)(2, 1).

None