Problem Statement

You are given integer sequences of length $N$, $A = (A_1, \dots ,A_N)$ and $B = (B_1, \dots ,B_N)$, and a positive integer $K$.

Each time you pay a cost of $1$, you can perform adjacent swaps exactly $K$ times. An adjacent swap refers to the following operation:

• Choose an integer $i$ between $1$ and $N-1$, inclusive, and swap $A_i$ and $A_{i+1}$.

Determine if it is possible to make $A$ match $B$. If possible, find the minimum cost required to make them match.

You are given $T$ test cases; find the answer for each of them.

Constraints

• $1 \le T \le 10^5$
• $2 \le N \le 3 \times 10^5$
• $1 \le K \le 10^9$
• $1 \le A_i,B_i \le N$
• $\{A_1,\dots ,A_N\}$ and $\{B_1,\dots ,B_N\}$ match as multisets.
• The sum of $N$ over all test cases is at most $3 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Output $T$ lines.

The $i$-th line should contain the minimum cost if it is possible to make $A$ match $B$ for the $i$-th test case, and -1 otherwise.