Nancy and Pranjali are best friends. For her birthday, Pranjali bought a beautiful bracelet for Nancy, made of ‘N’ multi-coloured pearls. Although stunned by the beauty of the pearls and touched by the gesture, Nancy felt that the arrangement of pearls could be changed somewhat, to make the bracelet even more beautiful. After thinking for a long time and making complex calculations, she came up with a formula to calculate the Elegance Factor (E) of the bracelet.

Starting from a particular pearl, she numbers all the pearls from 0 to N-1. Next, she assigns a numeric value to each distinct colour of the pearls, based on RGB values. Thus the bracelet can be represented by a circular integer array ‘A’ of size N. Also she comes up with another array, ‘B’ also of size N. Now, the Elegance Factor is given by:

Obviously, Nancy wants to find an arrangement with the maximum value of E. If there are multiple such arrangements, then she wants the lexicographically smallest one.

Once she has found the required arrangement, Nancy proceeds to re-arrange the pearls in the bracelet. However, Pranjali does not like the fact that her friend is making so many changes to her gift. To make her task much harder, she gives Nancy a number, D, and tells her that in 1 move, she can interchange the positions of 2 pearls only if they are at a distance D from each other.

Nancy does not want to upset her friend, but she also wants to finish the rearrangement as fast as possible. Can you help her find the minimum number of moves to finish the re-arrangement? If it is not possible to reach the desired arrangement, output -1.

Note 1: In case of multiple possible arrangements with the maximum elegance factor, the desired one is always the lexicographically smallest one, irrespective of whether it can be reached or not.

Note 2: There can be at most 3 distinct colours of the pearls in the bracelet

Note 3: Remember, the bracelet is circular. The distance D can be in both directions.

Input

First line contains T, the number of test cases.

First line of each test case contains 2 space separated integers, N and D.

The next line contains N space separated integers representing array A.

The next line contains N space separated integers representing array B.

Output

Output a single integer, the minimum number of moves, or -1 if not possible.

Constraints

1 ≤ T ≤ 5

2 ≤ N ≤ 14

1 ≤ D ≤ N-1

1 ≤ A[i] ≤ 1000000

0 ≤ B[i] ≤ 1000000

Example

Input:
1
5 1
2 3 4 2 3
0 0 0 0 0

Output:
3

Explanation

For all arrangements, E = 0. Therefore the desired arrangement is the lexicographically

smallest one i.e. 2 2 3 3 4.

The 3 pairs of indices to be exchanged (in order) to achieve this are (0 based indexing):

(i) 2-3;

(ii) 3-4;

(iii) 1-2;