ADASEED - Ada and Tulips

no tags 

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

Harsh warning: I'm verry sorry but I don't (currently) have tester, so the only one who tested the correctness was me myself (so there is big percentage of problem being wrong). In this case I apologise (this warning will be withdrawn as soon as Blue.Mary will get AC :P ).


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*105), the number of tulips and the number of colors.

Each of next 2 lines will contain N integers 0≤ Ai < 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 106


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

Example Input

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


hide comments
morass: 2017-06-19 23:37:12

@febrianandawp: Thanx: Yes, seems your solution is very similar to Blue.Marry's one ^_^

febrianandawp: 2017-06-19 16:21:07

nice problem, my code run 16.50s total : )

morass: 2017-06-17 14:14:13

@Min_25: Anyway seems master Blue.Marry managed it under 3sec (while managing to convers one "L" to "logN" from mine complexity ^_^ )

Min_25: 2017-06-17 13:54:46

I'm sorry, I meant it as "the displayed time" at a statistics or status page.
Thank you !

morass: 2017-06-17 12:32:20

@Min_25: What you mean by "total running time"? (like the sum is ~33s, ta maximum is ~6s)

Min_25: 2017-06-17 09:46:40

Could you tell me the total running time of your solution ?

morass: 2017-06-17 01:55:08

@feodorv: Thanx - hopefully it is repaired :D

feodorv: 2017-06-17 00:42:21

I am very sorry, couldn't you fix the problem statement in the following line: "Each of the next T test-cases begins with two integers: N, L (1 ≤ L ≤ N ≤ 2*105), the number of farmhouses and the number of fields." I mean N stands for the number of seeds for one row and L - for the numbers of colors)))

Added by:morass
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)