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

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define call(x)#x
#define fo(i,n)        for(int i=0;i<n;i++)
#define Fo(i,k,n)    for(int i=k;i<n;i++)
#define vi            vector<int>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pi 3.1415926535

typedef long long ll;
typedef unsigned long long ull;
ll mod = (ll) 1e9 + 7;

#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x) ;  cerr<< "\n";
#else
#define debug(x)
#endif
void _print(int a) {cerr << a;}
void _print(bool a) {cerr << a;}
void _print(ull a) {cerr << a;}
void _print(ll a) {cerr << a;}
void _print(double a) {cerr << a;}
void _print(string s) {cerr << s;}

///////////////
template <class T> void _print(std::vector<T> v) {cerr << "[ "; for (T i  : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(std::set<T>s) {cerr << "[ "; for (T i  : s) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(std::multiset<T>s) {cerr << "[ "; for (T i  : s) {_print(i); cerr << " ";} cerr << "]";}
///////////////
ll mod_add(ll a, ll b, ll M) {a = a % M; b = b % M; return (((a + b) % M) + M) % M;}
ll mod_mul(ll a, ll b, ll mod) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}
ll mod_sub(ll a, ll b, ll M) {a = a % M; b = b % M; return (((a - b) % M) + M) % M;}
//ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, modInverse(b, m), m) + m) % m;} //only for prime m
// ll phin(ll n) {ll number = n; if ((n) % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))

typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update > pbds;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set


// for (auto it = mp.begin(); it != mp.end(); it++)
// {
//     cout << it->first << " " << it->second << "\n";
// }


ll ceil2(ll a, ll b) {
    ll c = a / b;
    if (c * b < a) c++;
    return c;
}

ll setBitNumber(ll n)
{

    // To find the position
    // of the most significant
    // set bit
    ll k = (ll)(log2(n));

    // To return the the value
    // of the number with set
    // bit at k-th position
    return  k;
}
bool pow2(ll n)
{
    if (n == 0)
        return false;

    return (ceil(log2(n)) == floor(log2(n)));
}

ll  nextPowerOf2(ll  n)
{
    ll  p = 1;
    if (n && !(n & (n - 1)))
        return n;

    while (p < n)
        p <<= 1;

    return p;
}

//log(b) number of bits in b
ll binpow(ll a, ll b, ll m) {
    if (b == 0)
        return 1;
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;  //b/=2;
    }
    return res;
}

ll fact(ll n);

ll nCr(ll n, ll r)
{
    return fact(n) / (fact(r) * fact(n - r));
}

// Returns factorial of n
ll fact(ll n)
{

    ll res = 1;
    for (ll i = 2; i <= n; i++)
        res = (res * i) % mod;
    return res;
}

struct neal {
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// Function to return LCM of two numbers
long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}


bool isPrime(ll n)
{
    // Corner case
    if (n <= 1)
        return false;

    // Check from 2 to square rt of n
    for (ll i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;

    return true;
}

//seive
// std::vector <int> prime;
// bool is_composite[mod];

// void sieve (int n) {
//     std::fill (is_composite, is_composite + n, false);
//     for (int i = 2; i < n; ++i) {
//         if (!is_composite[i]) prime.push_back (i);
//         for (int j = 0; j < (int)prime.size () && i * prime[j] < n; ++j) {
//             is_composite[i * prime[j]] = true;
//             if (i % prime[j] == 0) break;
//         }
//     }
// }

vector<ll>primef;
void primeFactors(ll n)
{
    while (n % 2 == 0)
    {
        // cout << 2 << " ";
        primef.push_back(2);
        n = n / 2;
    }

    for (ll i = 3; i <= (ll)sqrt(n); i = i + 2)
    {
        while (n % i == 0)
        {
            // cout << i << " ";
            primef.push_back(i);
            n = n / i;
        }
    }

    if (n > 2) {
        primef.push_back(n);
    }
}


vector<ll>proper_d;
void divisors(ll num)
{
    ll result = 0;
    if (num == 1) {
        proper_d.push_back(result);
        return ;
    }
    for (ll i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            if (i == (num / i))
                proper_d.push_back(i);
            else {
                proper_d.push_back(i);
                proper_d.push_back(num / i);
            }
        }
    }

    proper_d.push_back(1);
    return;
}




ll binaryToDecimal(string n)
{
    string num = n;
    ll dec_value = 0;

    // Initializing base value to 1, i.e 2^0
    ll base = 1;

    ll len = num.length();
    for (ll i = len - 1; i >= 0; i--) {
        if (num[i] == '1')
            dec_value += base;
        base = base * 2;
    }

    return dec_value;
}

ll findMean(vector<ll>a, ll n)
{
    ll sum = 0;
    for (ll i = 0; i < n; i++)
        sum += a[i];

    return (ll)sum / (ll)n;
}

vector<ll>med;
// Function for calculating median
void findMedian( vector<ll>a, ll n)
{
    // First we sort the array
    sort(all(a));

    // check for even case
    if (n % 2 != 0) {
        med.push_back(a[n / 2]);
        return ;
    }
    med.push_back(a[(n - 1) / 2]);
    med.push_back((a[n / 2]));

    return ;
}


ll powerTow(ll a) {
    ll x = 1;
    fo(i, a) {
        x *= 2;
    }
    return x;
}


bool isComposite(ll  i)
{
    for ( ll  j = 2; j < i; j++)
    {
        if (i % j == 0)
        {   return true;    }
    }
    return false;
}

bool sorn(const pair<int, int> &a,
          const pair<int, int> &b)
{
    return (a.first > b.first);

    if (a.first == b.first)
        return (a.second < b.second);
}

// (int) (n*10) % 10
// int result = (static_cast<int>(res * 10)) % 10;




ll evenSum(ll n)
{
    // required sum
    return (n * (n + 1)) ;
}

bool isPalindrome(string S)
{
    // Stores the reverse of the
    // string S
    string P = S;

    // Reverse the string P
    reverse(P.begin(), P.end());

    // If S is equal to P
    if (S == P) {
        // Return "Yes"
        return 1;
    }
    // Otherwise
    else {
        // return "No"
        return 0;
    }
}

/* Get the rightmost set bit in set_bit_no */
//set_bit_no = Xor & ~(Xor - 1);



void solve()
{

    ll n, k;
    cin >> n >> k;
    vector<ll>v(n);
    int cntn1 = 0;
    map<ll, ll>mp1;
    for (ll i = 0; i < n; i++) {
        cin >> v[i];
        if (v[i] > 1)
            cntn1++;

        mp1[v[i]]++;
    }
    int i = n - 1;
    sort(all(v));
    int ans = 0;

    if (cntn1 < k)
    {

        for (int i = 0; i < n; i++)
        {

            if (v[i] > 1) {
                mp1[v[i]]--;
                mp1[1]--;
                k--;
            }
        }

        while (k > 0)
        {
            mp1[1] -= 2;
            ans++;
            k--;
        }

        for (auto it : mp1)
        {
            ans += it.first * it.second;
        }

        cout << ans << "\n";
        return;




    }

    while (k > 0)
    {

        if (v[i] == v[i - 1] && i - 1 >= 0)
        {
            ans++;
        }

        i -= 2;
        k--;

    }
    debug(ans)
    debug(v)
    debug(i)

    for (int j = 0; j <= i; j++)
    {
        ans += v[j];
    }

    cout << ans << "\n";





}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << fixed;
    cout << setprecision(10);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
#endif




    ll t = 1;

    cin >> t;
    while (t-- > 0)
    {
        //     //cout << "Case #" << tc << ": ";
        solve();
        // tc++;
    }

}