It is the beginning of the day at a bank, and a crowd of N clients is already waiting for the entrance door to open. Once the bank opens, no more clients arrive, and E employees begin serving the clients. An employee takes T minutes to serve each client. How long each client has already been waiting at the moment when the bank door opens is also given. You have to determine the best way to arrange the clients into E queues so that the waiting time of the client who waits longest is minimized. The waiting time of a client is the sum of the time the client waited outside before the bank opened, the time the client waited in a queue once the bank opened until the service began, and the service time of the client.

Input

First line contains k (the number of test cases). Then k test cases follows. First line of each test case contains N, E and T as described above. Next line contains N integers t1, t2 ... tn, ith of which is the waiting time of ith client before the opening of door.

Constraints

1 <= k <= 25, 1 <= N <= 50, 1 <= E <= 50, 1 <= T <= 100, 0 <= ti <= 100

Output

For each test case print in a separate line the minimum waiting time for the client who waits the longest.

Example

Input:
3
2 1 10
1 2
1 50 50
10
5 3 10
2 4 6 3 5

Output:
21
60
23