ADASEED  Ada and Tulips
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 testcases.
Each of the next T testcases begins with two integers: N, L (1 ≤ L ≤ N ≤ 2*10^{5}), 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 testcases won't exceed 10^{6}
Output
For each testcase 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
hide comments
morass:
20170619 23:37:12
@febrianandawp: Thanx: Yes, seems your solution is very similar to Blue.Marry's one ^_^ 

febrianandawp:
20170619 16:21:07
nice problem, my code run 16.50s total : ) 

morass:
20170617 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:
20170617 13:54:46
@morass


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

Min_25:
20170617 09:46:40
@morass


morass:
20170617 01:55:08
@feodorv: Thanx  hopefully it is repaired :D 

feodorv:
20170617 00:42:21
I am very sorry, couldn't you fix the problem statement in the following line: "Each of the next T testcases 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 
Date:  20170616 
Time limit:  8s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 