It is little John's birthday, and he has just received n boxes of chocolates as presents from his friends and family (1 < n ≤ 50). Now his mother knows that if she allows him to keep all the chocolates for himself, then he will definitely eat them all and end up with a stomach ache. So she instructs John to give one box each to each of the students in his class (excluding himself).

Now John's class has k students, excluding himself, (1 ≤ k < 50) and the ith box of chocolates contains exactly a[i] chocolates inside (1 ≤ a[i] ≤ 1000). So John obviously wants to select the k boxes such that the sum of the chocolates in the remaining (n-k) boxes is maximized, so he has more chocolates for himself.

This would be an easy task, except that John is very superstitious and wants to select these boxes in a very specific manner. He considers the number 4 and all its multiples to be extremely unlucky, and at no stage does he want the number of chocolates that he has to be a multiple of 4. Luckily, the sum of all the chocolates in all the n boxes is not a multiple of 4, and he wants to keep things that way.  So, while distributing the boxes, he will only consider handing out a box, if the sum of the remaining chocolates that he has is not a multiple of 4.

John is confused as to how he should do this, so please help him out. Your task is to help John select k boxes from the n boxes one at a time, such that at no stage is the number of remaining chocolates a multiple of 4, and such that the final number of chocolates remaining with John is maximized (and also not a multiple of 4).

NOTE : At every step, the sum of the chocolates in the remaining boxes must not be a multiple of 4. That is, after handing out the ith box, (1 ≤ i ≤ k), the sum of the chocolates in the remaining (n-i) boxes should not be a multiple of 4.

Input

In the first line we have a single integer T - the number of test cases (T ≤ 55). Then T test cases follow.

Each test case contains 2 lines. The first line contains 2 space separated numbers - n, the number of boxes (1 < n ≤ 50), and k, the number of students in John's class, excluding himself (1 ≤ k < 50)

The second line contains n space separated numbers, such that the ith number (a[i]) denotes the number of chocolates in the ith box (1 ≤ a[i] ≤ 1000).

Output

For each test case, on a single line, print the maximum possible chocolates that John can end up with after a valid distribution sequence. Print -1 if no such distribution exists.

Example

Input:
2
6 3
1 1 1 1 1 1
8 6
1 6 1 10 1 2 7 11

Output:
-1
21

Explanation

For the first case, the initial total number of chocolates is 6. After giving away any one of the boxes, the sum of chocolates remaining with John becomes 5. At this point, it becomes impossible to select any of the remaining boxes without making the sum with John a multiple of 4.

For the second test case, the maximum chocolates that can remain with John after a valid distribution sequence is 21.