As you might already know, Ada the Ladybug is a farmer. She decided to plant two similar rows of of tulips. She bought 2*N seeds of L different colors and planted them (in both rows) in such way, that the tulip of some color was L units far from nearest tulip of the same color. As Ada is also a mathematician, she gave you a more formal description: The i^th position had colod i % L (where % stands for modulo).

Even though she tried hard, she didn't expect the power of nature. A hurricane appeared and permuted the seeds in both rows (each seed remained in the same row, but got possibly different possition in it). Now the tulips grew but the rows doesn't have the same sequences of colors.

Ada doesn't like that, so she wants to rip off the least number of tulips so that both rows will have same sequence of colors.

Input

The first line contains an integer 1 ≤ T ≤ 1000, the number of test-cases.

Each of the next T test-cases begins with two integers: N, L (1 ≤ L ≤ N ≤ 2*10⁵), the number of tulips and the number of colors.

Each of next 2 lines will contain N integers 0≤ A_i < L, the colors of tulips.

As ada likes diversity, so she also assures you that N/L (integer division) won't exceed 100.

The sum of N over all test-cases won't exceed 10⁶

Output

For each test-case output the minimal number of tulips, which has to be ripped to achieve same sequences

Example Input

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

Example Output

6
2
0
4