Ankul and Rohil have been awarded with N gold coins in a recent programming competition. Now they want to divide these N coins. But there is a problem, weight of each coin is not equal. Both of them know that dividing these coins optimally is an NP-Complete problem. So they have decided to put all the coins on a stack and divide them in the following manner: 

They both take their turn alternatively and in each turn at most K coins from the top of stack can be taken. Ankul always start first. Consider that both of them are infinitely intelligent so they will always take the best possible move. you have to find the maximum weight which Ankul and Rohil will be able to get.

Input

First line of input contains T (1<=T<=30) the number of test cases then T test cases follow. First line of each test cases contains two space separated integers N and K (1<=N<=10000 and 1<=K<=10). 2nd line contains N space separated integers (w1, w2,...wn), wi if the weight of ith gold coins from the top.(0<=wi<=1000)

Output

For each test case print one line which contains 2 space separated integers A and R. A and R are the maximum weight of gold which Ankul and Rohil will be able to take respectively.

Example

Input:
2
3 2
1 2 3
10 4
2 1 0 1 3 9 2 0 1 5

Output:
3 3
14 10