Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4003
Distance

Time Limit: 3 Seconds      Memory Limit: 65536 KB

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


Author: ZHANG, Yuan
Source: ZOJ Monthly, January 2018
Submit    Status