import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main
(String[] args
) { try {
int t
= Integer.
parseInt(br.
readLine()); int n = 0, k = 0;
Integer value
= 0, reqCnt
= 0, demand
= 0; TreeMap
<String, Integer
> table
= new TreeMap
<String, Integer
>(); HashMap
<Integer, Integer
> reqCntTable
= new HashMap
<Integer, Integer
>();
for (int i = 0; i < t; i++) {
reqCntTable.clear();
table.clear();
data = br.readLine().split(" ");
data = br.readLine().split(" ");
if (k == 1) {
continue;
}
for (int j = 0; j < n; j++) {
key = data[j].trim();
value = table.get(key);
if (value == null) {
value = 0;
}
value++;
value = value % k;
table.put(key, value);
}
Collection<Integer> boquey = table.values();
ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
int hlen=heights.size();
while(iterator.hasNext()){
keyStr
=(String) iterator.
next(); demand = (k -table.get(keyStr));
reqCnt = reqCntTable.get(demand);
if (reqCnt == null) {
reqCnt = 1;
}else{
reqCnt++;
}
reqCntTable.put(demand, reqCnt);
}
long result = 0L;
int len = heights.size();
int freePool = 0, cpool = 0;
int j = 0;
int bqCnt=0;
int reqAux = 0;
for (j = len - 1; j > 0; j--) {
cpool = heights.get(j);
reqAux = k - cpool;
available = reqCntTable.get(cpool);
if ((available != null) && (available >0)) {
int index=heights.indexOf(cpool);
heights.set(index, 0);
result+=cpool;
available--;
reqCntTable.put(cpool, available);
reqAux = k - cpool;
available = reqCntTable.get(reqAux);
available--;
reqCntTable.put(reqAux, available);
}else{
freePool += cpool;
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
}
}
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
result += freePool;
table.clear();
}
}
}
}
aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7CmltcG9ydCBqYXZhLmlvLklPRXhjZXB0aW9uOwppbXBvcnQgamF2YS5pby5JbnB1dFN0cmVhbVJlYWRlcjsKaW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuQ29sbGVjdGlvbjsKaW1wb3J0IGphdmEudXRpbC5IYXNoTWFwOwppbXBvcnQgamF2YS51dGlsLkl0ZXJhdG9yOwppbXBvcnQgamF2YS51dGlsLlNldDsKaW1wb3J0IGphdmEudXRpbC5UcmVlTWFwOwogCnB1YmxpYyBjbGFzcyBNYWluIHsKIAoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCXRyeSB7CgkJCUJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKCQkJaW50IHQgPSBJbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkpOwoJCQlpbnQgbiA9IDAsIGsgPSAwOwoJCQlTdHJpbmcga2V5ID0gbnVsbDsKCQkJSW50ZWdlciB2YWx1ZSA9IDAsIHJlcUNudCA9IDAsIGRlbWFuZCA9IDA7CgkJCVRyZWVNYXA8U3RyaW5nLCBJbnRlZ2VyPiB0YWJsZSA9IG5ldyBUcmVlTWFwPFN0cmluZywgSW50ZWdlcj4oKTsKCQkJSGFzaE1hcDxJbnRlZ2VyLCBJbnRlZ2VyPiByZXFDbnRUYWJsZSA9IG5ldyBIYXNoTWFwPEludGVnZXIsIEludGVnZXI+KCk7CgkJCVN0cmluZyBkYXRhW10gPSBudWxsOwogCgkJCWZvciAoaW50IGkgPSAwOyBpIDwgdDsgaSsrKSB7CgkJCQlyZXFDbnRUYWJsZS5jbGVhcigpOwoJCQkJdGFibGUuY2xlYXIoKTsKCQkJCWRhdGEgPSBici5yZWFkTGluZSgpLnNwbGl0KCIgIik7CgkJCQluID0gSW50ZWdlci5wYXJzZUludChkYXRhWzBdKTsKCQkJCWsgPSBJbnRlZ2VyLnBhcnNlSW50KGRhdGFbMV0pOwogCgkJCQlkYXRhID0gYnIucmVhZExpbmUoKS5zcGxpdCgiICIpOwoJCQkJaWYgKGsgPT0gMSkgewoJCQkJCVN5c3RlbS5vdXQucHJpbnRsbigwKTsKCQkJCQljb250aW51ZTsKCQkJCX0KCQkJCWZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKSB7CgkJCQkJa2V5ID0gZGF0YVtqXS50cmltKCk7CgkJCQkJdmFsdWUgPSB0YWJsZS5nZXQoa2V5KTsKCQkJCQlpZiAodmFsdWUgPT0gbnVsbCkgewoJCQkJCQl2YWx1ZSA9IDA7CiAKCQkJCQl9CgkJCQkJdmFsdWUrKzsKCQkJCQl2YWx1ZSA9IHZhbHVlICUgazsKCQkJCQl0YWJsZS5wdXQoa2V5LCB2YWx1ZSk7CiAKCQkJCgkJCQl9CgkJCQlDb2xsZWN0aW9uPEludGVnZXI+IGJvcXVleSA9IHRhYmxlLnZhbHVlcygpOwoJCQkJQXJyYXlMaXN0PEludGVnZXI+IGhlaWdodHMgPSBuZXcgQXJyYXlMaXN0PEludGVnZXI+KGJvcXVleSk7CgkJCQlpbnQgaGxlbj1oZWlnaHRzLnNpemUoKTsKCQkJCQoJCQkJU2V0IGtleXM9dGFibGUua2V5U2V0KCk7CgkJCQlJdGVyYXRvciBpdGVyYXRvcj1rZXlzLml0ZXJhdG9yKCk7CgkJCQlTdHJpbmcga2V5U3RyPSIiOwoJCQkJCgkJCQl3aGlsZShpdGVyYXRvci5oYXNOZXh0KCkpewoJCQkJCWtleVN0cj0oU3RyaW5nKSBpdGVyYXRvci5uZXh0KCk7CgkJCQkJZGVtYW5kID0gKGsgLXRhYmxlLmdldChrZXlTdHIpKTsKCQkJCQlyZXFDbnQgPSByZXFDbnRUYWJsZS5nZXQoZGVtYW5kKTsKCQkJCQlpZiAocmVxQ250ID09IG51bGwpIHsKCQkJCQkJcmVxQ250ID0gMTsKCQkJCQl9ZWxzZXsKCQkJCQkJcmVxQ250Kys7CgkJCQkJfQoJCQkJCXJlcUNudFRhYmxlLnB1dChkZW1hbmQsIHJlcUNudCk7CgkJCQl9CgkJCQkKIAoJCQkJbG9uZyByZXN1bHQgPSAwTDsKCQkJCWludCBsZW4gPSBoZWlnaHRzLnNpemUoKTsKCQkJCWludCBmcmVlUG9vbCA9IDAsIGNwb29sID0gMDsKCQkJCUludGVnZXIgYXZhaWxhYmxlID0gMDsKCQkJCWludCBqID0gMDsKCQkJCWludCBicUNudD0wOwoJCQkJaW50IHJlcUF1eCA9IDA7CiAKCQkJCWZvciAoaiA9IGxlbiAtIDE7IGogPiAwOyBqLS0pIHsKCQkJCQljcG9vbCA9IGhlaWdodHMuZ2V0KGopOwoJCQkJCXJlcUF1eCA9IGsgLSBjcG9vbDsKCQkJCQlhdmFpbGFibGUgPSByZXFDbnRUYWJsZS5nZXQoY3Bvb2wpOwoJCQkJCWlmICgoYXZhaWxhYmxlICE9IG51bGwpICYmIChhdmFpbGFibGUgPjApKSB7CgkJCQkJCWludCBpbmRleD1oZWlnaHRzLmluZGV4T2YoY3Bvb2wpOwoJCQkJCQloZWlnaHRzLnNldChpbmRleCwgMCk7CgkJCQkJCXJlc3VsdCs9Y3Bvb2w7CgkJCQkJCWF2YWlsYWJsZS0tOwoJCQkJCQlyZXFDbnRUYWJsZS5wdXQoY3Bvb2wsIGF2YWlsYWJsZSk7CgkJCQkJCXJlcUF1eCA9IGsgLSBjcG9vbDsKCQkJCQkJYXZhaWxhYmxlID0gcmVxQ250VGFibGUuZ2V0KHJlcUF1eCk7CgkJCQkJCWF2YWlsYWJsZS0tOwoJCQkJCQlyZXFDbnRUYWJsZS5wdXQocmVxQXV4LCBhdmFpbGFibGUpOwoJCQkJCX1lbHNlewoJCQkJCQlmcmVlUG9vbCArPSBjcG9vbDsKCQkJCQkJYnFDbnQ9ZnJlZVBvb2wvazsKCQkJCQkJZnJlZVBvb2w9ZnJlZVBvb2wlazsKCQkJCQkJcmVzdWx0Kz0oay0xKSpicUNudDsKCQkJCQl9CgkJCQl9CiAKCQkJCWJxQ250PWZyZWVQb29sL2s7CgkJCQlmcmVlUG9vbD1mcmVlUG9vbCVrOwoJCQkJcmVzdWx0Kz0oay0xKSpicUNudDsKCQkJCQoJCQkJcmVzdWx0ICs9IGZyZWVQb29sOwoJCQkJdGFibGUuY2xlYXIoKTsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbihyZXN1bHQpOwoJCQl9CgkJfSBjYXRjaCAoSU9FeGNlcHRpb24gZXgpIHsKCQl9CiAKCX0KIAp9IA==