You are given an array a of n integers, and another integer k such that 2k ≤ n.

You have to perform exactly k operations with this array. In one operation, you have to choose two elements of the array (let them be a_i and a_j; they can be equal or different, but their positions in the array must not be the same), remove them from the array, and add ⌊ (a_i)/(a_j) ⌋ to your score, where ⌊ x/y ⌋ is the maximum integer not exceeding x/y.

Initially, your score is 0. After you perform exactly k operations, you add all the remaining elements of the array to the score.

Calculate the minimum possible score you can get.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 500) — the number of test cases.

Each test case consists of two lines. The first line contains two integers n and k (1 ≤ n ≤ 100; 0 ≤ k ≤ ⌊ n/2 ⌋).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5).

Output

Print one integer — the minimum possible score you can get.

Example

Input


5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
9 2
1 10 10 1 10 2 7 10 3


Output


2
16
0
6
16

Note

Let's consider the example test.

In the first test case, one way to obtain a score of 2 is the following one:

  1. choose a_7 = 1 and a_4 = 2 for the operation; the score becomes 0 + ⌊ 1/2 ⌋ = 0, the array becomes [1, 1, 1, 1, 3]; 
  2. choose a_1 = 1 and a_5 = 3 for the operation; the score becomes 0 + ⌊ 1/3 ⌋ = 0, the array becomes [1, 1, 1]; 
  3. choose a_1 = 1 and a_2 = 1 for the operation; the score becomes 0 + ⌊ 1/1 ⌋ = 1, the array becomes [1]; 
  4. add the remaining element 1 to the score, so the resulting score is 2. 



In the second test case, no matter which operations you choose, the resulting score is 16.

In the third test case, one way to obtain a score of 0 is the following one:

  1. choose a_1 = 1 and a_2 = 3 for the operation; the score becomes 0 + ⌊ 1/3 ⌋ = 0, the array becomes [3, 7]; 
  2. choose a_1 = 3 and a_2 = 7 for the operation; the score becomes 0 + ⌊ 3/7 ⌋ = 0, the array becomes empty; 
  3. the array is empty, so the score doesn't change anymore. 



In the fourth test case, no operations can be performed, so the score is the sum of the elements of the array: 4 + 2 = 6.
1
6 3
4 4 5 5 6 6
 1
6 3
1 1 1 1 2 2
 1
9 3
1 1 1 2 2 2 3 3 3
 1
10 5
3 3 3 4 4 4 5 5 5 1
 1
10 4
1 1 1 2 3 3 3 3 4 5
 1
77 9
9 8 10 5 8 20 17 19 14 16 7 6 15 16 6 13 10 13 14 12 5 6 12 14 12 8 13 12 17 8 12 17 2 11 8 18 17 2 13 2 1 19 9 8 10 20 8 12 15 1 3 15 6 19 4 11 12 8 3 2 1 20 15 14 6 10 11 1 5 11 10 6 20 6 14 16 6
 1
14 7
1 1 1 1 1 1 1 2 2 2 2 2 3 3
 1
88 38
9 143 135 72 74 12 120 27 108 183 18 24 163 122 140 155 166 188 197 14 134 66 188 161 79 100 40 55 161 118 121 18 72 141 136 31 39 187 2 98 16 118 120 196 127 66 135 186 49 16 17 50 107 192 50 23 62 110 83 124 197 127 185 129 131 182 45 147 174 115 89 109 177 7 70 43 75 5 157 93 59 26 176 105 32 89 65 6
 5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
10 5
3 3 3 4 4 4 5 5 5 1
 1
87 12
10 5 11 7 16 16 8 11 14 11 4 4 3 7 16 12 2 3 3 13 1 7 11 16 4 7 11 5 3 15 20 5 12 1 8 8 13 19 3 7 14 3 4 10 18 13 20 1 4 8 10 12 4 7 15 2 18 13 6 2 1 2 10 13 4 5 18 7 1 10 6 2 19 17 5 11 10 12 14 6 16 20 11 12 10 3 6
 1
16 8
1 1 2 2 3 3 3 3 3 3 3 3 3 4 5 5
 1
8 4
1 1 3 3 3 3 5 6
 1
12 6
1 1 1 8 8 8 8 8 8 10 10 10
 5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
6 3
2 2 3 3 4 4
9 2
1 10 10 1 10 2 7 10 3
 1
12 6
1 1 1 1 1 2 2 2 2 3 3 3
 1
100 34
2 6 5 4 4 4 5 7 6 6 1 2 5 1 4 4 4 5 5 5 2 3 5 6 6 1 1 3 7 5 4 4 1 3 4 6 4 2 7 6 5 4 6 1 1 2 4 6 4 2 2 6 6 3 5 3 4 5 3 4 3 2 1 7 7 5 4 6 3 1 6 7 6 2 2 2 4 7 3 2 6 1 1 3 1 5 6 4 4 7 2 6 6 5 4 4 3 5 2 4
 1
85 3
43 17 34 67 14 7 80 48 36 95 48 68 86 4 17 46 51 87 41 90 100 56 57 42 9 8 27 23 16 14 99 22 13 98 89 24 77 59 15 94 25 81 4 71 24 43 97 88 97 10 6 8 3 86 28 61 100 98 76 85 32 18 79 66 51 44 28 99 87 56 80 93 89 76 7 57 96 39 46 25 4 67 6 51 39
 1
6 3
1 1 2 2 3 3
 1
6 3
2 3 3 3 4 4
 1
6 3
1 7 7 7 10 10
 1
10 3
1 7 4 3 2 2 6 7 4 7
 1
100 17
5 1 1 7 3 2 5 1 1 3 4 5 5 5 7 5 7 5 1 7 6 6 1 3 6 3 4 5 4 6 3 1 7 6 2 3 2 5 3 3 6 5 5 6 5 7 5 3 5 4 7 3 5 1 7 3 4 4 3 3 3 5 1 1 1 7 1 3 2 3 2 7 2 1 6 5 6 6 1 5 4 6 1 7 6 7 6 1 1 1 5 3 5 7 4 6 4 6 3 2
 1
7 3
1 1 1 2 2 3 3
 1
9 2
1 10 10 1 10 2 7 10 191919
 1
6 3
6 6 5 5 1 1
 1
8 3
1 1 6 6 6 6 2 2
 1
91 9
4 3 19 8 3 6 16 5 17 11 9 13 15 8 1 3 20 2 19 7 14 1 6 4 8 18 13 8 16 11 3 12 3 3 12 17 15 9 5 15 12 11 7 20 19 3 4 14 10 9 7 16 12 10 3 6 15 17 4 8 15 2 10 13 11 15 7 20 1 10 9 2 10 15 7 1 6 16 2 1 17 10 19 10 7 18 3 5 10 12 15
 1
67 22
83 41 94 76 47 33 20 51 98 48 92 72 24 51 15 17 35 70 83 95 79 65 80 17 72 7 97 14 74 98 55 63 45 79 42 92 85 24 84 30 29 77 64 68 68 71 89 18 82 68 20 91 84 52 45 23 65 95 83 84 18 81 63 11 89 41 69
 1
4 2
5 6 5 5
 1
6 3
3 3 4 4 7 7
 10
7 3
2 2 2 2 3 3 3
7 3
2 2 3 3 3 4 4
7 3
2 2 2 2 2 2 2
7 3
2 2 3 3 3 4 4
7 3
2 2 2 3 3 3 3
7 3
2 2 3 3 3 3 4
7 3
2 2 2 2 2 3 3
7 3
2 2 3 3 3 3 3
7 3
2 2 2 2 2 2 3
7 3
2 2 2 3 3 3 4
 1
7 3
2 2 2 2 7 8 2
 1
13 6
1 2 2 2 2 3 3 3 3 4 4 4 4
 1
10 3
1 1 1 1 1 1 2 2 3 3
 1
10 3
2 15 14 13 12 15 18 2 9 15
 1
8 4
1 2 2 2 2 3 3 3

0
 1
 3
 0
 2
 489
 0
 140
 2
16
0
6
0
 401
 1
 0
 0
 2
16
0
0
16
 0
 58
 3753
 0
 0
 0
 8
 192
 1
 22
 0
 3
 569
 616
 1
 0
 2
2
5
2
3
3
3
4
4
2
 3
 1
 4
 25
 0

import java.io.*;
import java.util.Arrays;
import java.util.*;
import java.util.Scanner;
import java.util.StringTokenizer;




public class copy {


    public static boolean checker(long[] arr, long K, long diff) {
        long collect = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > diff)
                collect += arr[i] - diff;
        }

        if (collect >= K)
            return true;
        else
            return false;
    }

    public static long search(long[] arr, long K, long R) {
        long l = 0;
        long r = R;

        while (l <= r) {
            long mid = (l + r) / 2;

            if (checker(arr, K, mid)) {
                if (checker(arr, K, mid + 1))
                    l = mid + 1;
                else
                    return mid;
            } else
                r = mid - 1;
        }
        return -1;
    }

    static void sieveOfEratosthenes(int n, ArrayList<Integer> arr, ArrayList<Integer> arr1) {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true) {

                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        int x = 0;
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true) {

                arr.add(i);


            }

        }
        System.out.println(arr.size());
    }

    public static boolean check(String s, int K, char ch) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ch)
                arr.add(i);
        }
//        if(K==1 && ch=='z')
//            System.out.println(arr);
        if (arr.size() == 0)
            return false;
        if (arr.get(0) >= K)
            return false;
        if (s.length() - 1 - arr.get(arr.size() - 1) >= K)
            return false;
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) - arr.get(i - 1) > K)
                return false;
        }
        return true;
    }

    public static int check(long N) {
        int sum = 0;
        while (N > 0) {
            sum += N % 10;
            N = N / 10;
        }
        return sum;

    }

    public static long call(long N) {
        long l = 1;
        long r = (long) Math.floor(Math.sqrt(N));
        while (l <= r) {
            long mid = (l + r) / 2;
            double left = N / (double) (mid) - mid;
            int right = check(mid);
            System.out.println(mid + " " + left + " " + right);
            if (mid == 10)
                System.out.println(left + " " + right);
            if (left > right)
                l = mid + 1;
            else if (right > left)
                r = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    public static int path(ArrayList<ArrayList<Integer>> arr, int X, int parent, int[] gold, PriorityQueue<Integer> pq) {
        int max = 0;
        ArrayList<Integer> ch = new ArrayList<>();
        for (int i : arr.get(X)) {
            if (i != parent) {
                ch.add(path(arr, i, X, gold, pq));
            }
        }
        Collections.sort(ch, Collections.reverseOrder());
        for (int i = 1; i < ch.size(); i++)
            pq.add(ch.get(i));


        if (ch.size() == 0)
            return gold[X];
        else
            return ch.get(0) + gold[X];

    }

    public static long fac(long N, long mod) {
        if (N == 0)
            return 1;
        if(N==1)
            return 1;
        return ((N % mod) * (fac(N - 1, mod) % mod)) % mod;
    }

    public static String form(char ch, int freq) {
        String s = "";
        for (int i = 1; i <= freq; i++)
            s += ch;
        return s;
    }

    static long power(long x, long y, long p) {

        // Initialize result
        long res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static long modInverse(long n, long p) {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static long nCrModPFermat(long n, long r,
                              long p) {

        if (n < r)
            return 0;
        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r


//        System.out.println(modInverse(fac(r,p),p));
//        System.out.println(modInverse(fac(n-r,p),p));
        return ((fac(n, p) % p * (modInverse(fac(r, p), p)
                % p)) % p * (modInverse(fac(n - r, p), p)
                % p)) % p;
    }

    public static boolean check(long[] arr, long time, int M) {
        long sum = 0;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum >= time) {
                ++count;
                sum = 0;
            }
        }

        if (sum >= time)
            ++count;

        return count >= M;
    }

    public static int check(ArrayList<Integer> arr, ArrayList<Integer> arr2) {
        int l = 0, r = 0, ans = 0;
        while (l < arr.size() && r < arr2.size()) {
            if (arr.get(l) < arr2.get(r))
                ++l;
            else if (arr.get(l) > arr2.get(r))
                ++r;
            else {
                ++ans;
                ++l;
                ++r;
            }
        }
        return ans;
    }


    public static int find(int[] parent, int x) {
        if (parent[x] == x)
            return x;
        return find(parent, parent[x]);
    }

    public static int merge(int[] parent, int[] rank, int x, int y,int[] child) {
        int x1 = find(parent, x);
        int y1 = find(parent, y);
        int c=0;
        if (rank[x1] > rank[y1]) {
            parent[y1] = x1;
            child[x1]+=child[y1];
            c=child[x1];

        } else if (rank[y1] > rank[x1]) {
            parent[x1] = y1;
            child[y1]+=child[x1];
            c=child[y1];
        } else {
            parent[y1] = x1;
            rank[x1]++;
            child[x1]+=child[y1];
            c=child[x1];
        }

        return c;
    }

    public static int bfs(ArrayList<ArrayList<Integer>> arr, int e1, int e2, int N) {
        boolean[] visited = new boolean[N];
        visited[0] = true;
        int[] dist = new int[N];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        Arrays.fill(dist, -1);
        dist[0] = 0;
        while (queue.size() > 0) {
            int x = queue.poll();
            for (int i : arr.get(x)) {
                if (!visited[i] || (e1 == x && e2 == i)) {
                    System.out.println(x + " " + dist[x]);
                    dist[i] = dist[x] + 1;
                    visited[i] = true;
                    queue.add(i);
                }
            }

        }


        return dist[N - 1];
    }








    public static int binarysearch(ArrayList<Integer> possible, int X, int start) {
        int l = start, r = possible.size() - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (possible.get(mid) > X) {
                if (mid - 1 >= start && possible.get(mid - 1) > X)
                    r = mid - 1;
                else
                    return mid;
            } else
                l = mid + 1;
        }

        return -1;
    }







    public static long gcd(long a, long b) {
        if (b == 0)
            return a;

        return gcd(b, a % b);
    }


    public static void leftRotatebyOne(int arr[], int n) {
        int i, temp;
        temp = arr[0];
        for (i = 0; i < n - 1; i++)
            arr[i] = arr[i + 1];
        arr[n - 1] = temp;
    }



    static int power(int x, int y, int p)
    {

        // Initialize result
        int res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static int modInverse(int n, int p)
    {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static int nCrModPFermat(int n, int r,
                             int p)
    {

        if (n<r)
            return 0;
        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r
        int[] fac = new int[n + 1];
        fac[0] = 1;

        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i % p;

        return (fac[n] * modInverse(fac[r], p)
                % p * modInverse(fac[n - r], p)
                % p)
                % p;
    }



    public static long[][] ncr(int n,int r)
    {
        long[][] dp=new long[n+1][r+1];
        for(int i=0;i<=n;i++)
            dp[i][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=r;j++)
            {
                if(j>i)
                    continue;
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            }
        }

        return dp;

    }

    static boolean status=false;
    static int x1=-1,y1=-1;
    public static int dfs(ArrayList<ArrayList<Integer>> arr,int X,int[] ans,int value,int parent)
    {
        int xor=ans[X];
        for(int i:arr.get(X))
        {
            if(i!=parent)
            {
                int x=dfs(arr,i,ans,value,X);
                if(x==-1)
                    return -1;
                if(x==value)
                {
                    x1=X;
                    y1=i;
                    return -1;
                }
                xor=xor^x;
            }
        }



        return xor;
    }

    public static boolean prime(long N)
    {
        int c=0;
        for(int i=2;i*i<=N;i++)
        {
            if(N%i==0)
                ++c;
        }

        return c==0;
    }
    static int[] c;
    static boolean sta=true;
    public static int dfs(ArrayList<ArrayList<Integer>> arr,int N,int j,int[] status,boolean[] visited)
    {
        Queue<Integer> queue=new LinkedList<>();
        queue.add(j);
        status[j]=1;
        visited[j]=true;
        int[] color=new int[2];
        while(queue.size()>0)
        {
            int temp=queue.poll();
            if(temp<N)
                color[status[temp]]++;
            for(int i:arr.get(temp))
            {
                if(visited[i])
                {
                    if(status[i]==status[temp])
                        return -1;
                }
                else
                {
                    queue.add(i);
                    status[i]=1-status[temp];
                    visited[i]=true;
                }
            }
        }

        return Math.max(color[0],color[1]);
    }

    public static boolean check(String s,int N,long D,long C,long M)
    {
        int index=s.lastIndexOf('D');
        for(int i=0;i<=index;i++)
        {
            if(s.charAt(i)=='D' && D>0)
            {
                D-=1;
                C+=M;
            }
            else if(s.charAt(i)=='C' && C>0)
            {
                C-=1;
            }
            else
                return false;
        }

        return true;
    }




    public static boolean checkbounds(int x,int y,int N,int M)
    {
        return x>=0 && x<N && y>=0 && y<M;
    }

    public static void dfs(int x,int y,char[][] grid,boolean[][] visited,int N,int M)
    {
        visited[x][y]=true;
        if(checkbounds(x+1,y,N,M) && !visited[x+1][y] && grid[x+1][y]=='.')
            dfs(x+1,y,grid,visited,N,M);
        if(checkbounds(x-1,y,N,M) && !visited[x-1][y] && grid[x-1][y]=='.')
            dfs(x-1,y,grid,visited,N,M);
        if(checkbounds(x,y+1,N,M) && !visited[x][y+1] && grid[x][y+1]=='.')
            dfs(x,y+1,grid,visited,N,M);
        if(checkbounds(x,y-1,N,M) && !visited[x][y-1] && grid[x][y-1]=='.')
            dfs(x,y-1,grid,visited,N,M);
    }

    public static int bin(ArrayList<Integer> arr,int search)
    {
        int l=0,r=arr.size()-1;
        if(search<arr.get(0))
            return -1;
        if(search>arr.get(r-1))
            return r+1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(arr.get(mid)>search)
            {
                if(mid-1>=0 && arr.get(mid-1)>search)
                    r=mid-1;
                else
                    return mid;
            }
            else
                l=mid+1;
        }

        return -1;
    }


    public static int mcbc(ArrayList<Long> arr,long search,int N,int lower)
    {
        if(search>=arr.get(N))
            return N;

        if(search<=arr.get(lower))
            return lower;
        int l=lower;
        int r=N;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(arr.get(mid)==search)
            {
                return mid;
            }

            if(arr.get(mid)>search)
            {
                if(mid-1>=lower && arr.get(mid-1)>=search)
                    r=mid-1;
                else
                {
                    if(mid-1>=lower)
                    {
                        if (Math.abs(search - arr.get(mid)) < Math.abs(search - arr.get(mid - 1)))
                            return mid;
                        else
                            return mid - 1;
                    }
                    else
                        return mid;
                }
            }

            else if(arr.get(mid)<search)
            {
                if(mid+1<=N && arr.get(mid+1)<=search)
                    l=mid+1;
                else
                {
                    if(mid+1<=N)
                    {
                        if (Math.abs(search - arr.get(mid)) < Math.abs(search - arr.get(mid + 1)))
                            return mid;
                        else
                            return mid + 1;
                    }
                    else
                        return mid;
                }
            }
        }

        return -1;

    }

    public static int check(String s,char ch)
    {
        int l=0,r=s.length()-1;
        int c=0;
        while(l<r)
        {
            if(s.charAt(l)!=s.charAt(r))
            {
                if(s.charAt(l)==ch)
                {
                    ++c;
                    ++l;
                }
                else if(s.charAt(r)==ch)
                {
                    ++c;
                    --r;
                }
                else
                {
                    return -1;
                }
            }
            else
            {
                ++l;
                --r;
            }
        }

        return c;

    }



    static boolean cycle=false;

    public static void check(int x1,int y1,String[][] s,boolean[][] visited,int N,int M,int[] xdiff,int[] ydiff,div[][] ans,int index)
    {
        Queue<div> queue1=new LinkedList<>();
        Queue<div> queue2=new LinkedList<>();
        visited[x1][y1]=true;
        queue1.add(new div(x1,y1));
        queue2.add(new div(x1,y1));
        int c=0;
        while(queue1.size()>0)
        {
            div temp=queue1.poll();
            //System.out.println("hello");
            int x=temp.x;
            int y=temp.y;
            ++c;
            for(int i=0;i<4;i++)
            {
                if(getbounds(x+xdiff[i],y+ydiff[i],N,M))
                {
                    if(!visited[x+xdiff[i]][y+ydiff[i]] && s[x+xdiff[i]][y+ydiff[i]].equals("."))
                    {
                        queue1.add(new div(x+xdiff[i],y+ydiff[i]));
                        queue2.add(new div(x+xdiff[i],y+ydiff[i]));
                        visited[x+xdiff[i]][y+ydiff[i]]=true;
                    }
                }
            }
        }

        div com=new div(index,c);

        while(queue2.size()>0)
        {

            div temp=queue2.poll();
            int x=temp.x;
            int y=temp.y;
            ans[x][y]=com;
        }

    }

    static int connected=0;

    public static int edges(ArrayList<ArrayList<Integer>> arr,int x,boolean[] visited)
    {
        ++connected;
        int sum=arr.get(x).size();
        visited[x]=true;
        for(int i:arr.get(x))
        {
            if(!visited[i])
                sum+=edges(arr,i,visited);
        }

        return sum;

    }





    public static boolean getbounds(int x,int y,int N,int M)
    {
        return x>=0 && x<N && y>=0 && y<M;
    }

    public static boolean drag(long h,ArrayList<Integer> interval,long mid)
    {
        long ans=0;
        for(int i=1;i<interval.size();i++)
        {
            ans+=Math.min(mid,interval.get(i)-interval.get(i-1));
        }
        ans+=mid;
        return ans>=h;
    }


    public static long search(ArrayList<Integer> interval,long h)
    {
        long l=1;long r=(long)Math.pow(10,18);
        while(l<=r)
        {
            long mid=(l+r)/2;
            if(drag(h,interval,mid))
            {
                if(mid-1>=1 && drag(h,interval,mid-1))
                    r=mid-1;
                else
                    return mid;
            }
            else
                l=mid+1;
        }

        return -1;

    }








    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        int T=Reader.nextInt();
        for(int m=1;m<=T;m++) {

          int N=Reader.nextInt();
          int K=Reader.nextInt();
          ArrayList<Long> arr=new ArrayList<>();
          long sum=0;
          for(int i=0;i<N;i++)
          {
              arr.add(Reader.nextLong());
              sum+=arr.get(i);
          }
//            System.out.println(sum);
          Collections.sort(arr);
          int r=N-1,store=K;
          while(K>0)
          {
              sum+=(arr.get(r-store))/(arr.get(r));
              sum-=arr.get(r-store);
              sum-=arr.get(r);
              --r;
              --K;
          }

          output.write(sum+"\n");


        }

















        output.flush();

    }
}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}


class sortat implements Comparator<div>
{
    public int compare(div o1,div o2)
    {
        return o1.x-o2.x;
    }
}

class div {
    int x, y;

    div(int x1,int z1) {
        x = x1;
        y=z1;

    }
}

class TreeNode
{
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int data)
    {
        left=null;
        right=null;
        this.data=data;
    }
}