Server Time: Tue Sep 29, 2020 12:53 am
Welcome ( logout
B - Colored T-Shirts
  PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

N students are standing in a line. They are wearing colored t-shirts. For simplicity, let's assume that the color of each person is an integer between 1 and 16. Like color 1 represents red, color 2 represents blue, and so on.

Now the students with same colored t-shirts want to join together. So, they are thinking what to do. That's why you are here to the rescue! You have to solve this problem. You have to say the minimum number of swaps necessary to reformat the line such that the people with same colored t-shirt come together. A swap means changing position between two adjacent people in the line.


Input starts with an integer T (≤ 15), denoting the number of test cases.

Each case starts with two integers N (1 ≤ N ≤ 105) and m (1 ≤ m ≤ 16), where m denotes the number of total colors. So, the students in the line will have a t-shirt color between 1 and m. The next line contains N space separated integers. Each of these integers will lie between 1 and m, denoting the color of the ith person in the line.


For each case, print the case number and the minimum number of swaps necessary to arrange them according to the description.

Sample Input

Output for Sample Input


4 2

1 2 1 2

6 4

2 1 4 3 1 2

8 6

1 3 2 5 5 4 5 2

Case 1: 1

Case 2: 6

Case 3: 5


Dataset is huge. Use faster i/o methods.

Problem Setter: Jane Alam Jan
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan