Time Limit: 1 s
Memory Limit: 32 MB

Submission：5
AC：3
Score：99.81

There are *n* students standing in a line, each of them is wearing clothes of one certain color. There is total *m* different colors, so each color can be represented by a single number from 0 to *m-1*.Teacher Wu wants to let his students wear clothes of the same color, so he need some operations. As we all know teacher Wu is an erratic person, if one student is wearing clothes of *i*-th color and teacher Wu wants to change this student’s color, he only asks this student to wear *((i+1)%m)*-th color in one operation. What’s more, in one operation, teacher Wu always let the *t* consecutive students change their colors. Now here comes the problem, give you the number *n*,*m*,*t*,（*n*<2000, *m*<150, *t*<n）and all students’ clothes color, you are required to calculate the least operations through which all the students can wear clothes of the same color.

In the first of the input, there is a number *k*<=30, indicating the number of test cases.

For every test case, there is one line containing three positive integers *n*, *m*, *t*, followed by some lines containing *n* numbers *ai *(0<=*ai*<=*m-1*) indicating the color of the *i*-th student’s clothes.

For each test case, you are to output two integers in one line, the minimal operations and the color these students wear at last. If there are two colors which can be achieved by the same number of operations, you need to output the small one. It’s guaranteed that you can find some operations getting the same color for all of the input.

input

1
7 2 3
0 0 1 0 1 0 0

output

3 1