#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define ep emplace
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mt make_tuple
#define fi first
#define se second
#define fastio ios::sync_with_stdio(false);cin.tie(NULL)
#define rng_23 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef LOCAL
#include "debug.h"
#else
#define dbg1(args...) ;
#define dbg2(x) ;
#define stop ;
#endif
typedef long long LL;
typedef pair<LL,int> pii;
typedef tuple<int ,int , int > tiii;
const LL INF=1e25;
const LL MOD=1000000007;

std::ostream&
operator<<( std::ostream& dest, __int128_t value )
{
    std::ostream::sentry s( dest );
    if ( s ) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[ 128 ];
        char* d = std::end( buffer );
        do
        {
            -- d;
            *d = "0123456789"[ tmp % 10 ];
            tmp /= 10;
        } while ( tmp != 0 );
        if ( value < 0 ) {
            -- d;
            *d = '-';
        }
        int len = std::end( buffer ) - d;
        if ( dest.rdbuf()->sputn( d, len ) != len ) {
            dest.setstate( std::ios_base::badbit );
        }
    }
    return dest;
}


LL ara[1000000];
void solve(int csno)
{
	int n, k;
	LL m;
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++	){
		cin >> ara[i];
	}

	sort(ara, ara + n);



	vector<__int128_t> extra(1, 0), pref(1, 0);
	for(int i = 1; i < n; i++){
		if(ara[i] == ara[i - 1])
			extra.pub(ara[i]);
	}

	for(int i = 1; i < extra.size(); i++)
		pref.pub(pref.back() + extra[i]);

	k++;

	__int128_t res = k<=pref.size()? pref[k - 1] : INF;

	vector<pii> bubs;
	for(int i = 0; i < n; i++){
		if(bubs.empty() or bubs.back().fi != ara[i]){
			bubs.pub({ara[i], 1});
		}
		else
			bubs.back().se++;
	}

	dbg2(bubs);

	__int128_t sub = 0;
	LL g = 0;
	for(int i = 0; i < bubs.size(); i++){
		if(bubs[i].se < k){
			sub += (__int128_t)bubs[i].fi * bubs[i].se;
			g = __gcd(g, bubs[i].fi);
			k -= bubs[i].se;
		}
		else {
			sub += (__int128_t)min(bubs[i].se, k - 1) * bubs[i].fi;

			LL mx = -INF;
			for(int j = i; j < bubs.size(); j++){
				mx = max(mx, __gcd(g, bubs[j].first) - bubs[j].first);
			}
			sub -= mx;
			break;
		}
	}
	dbg1(sub);
	res = min(res, sub);

	__int128_t sum = 0;
	for(int i = 0; i < n; i++)
		sum += ara[i];

	res = sum - res;

	cout<<res<<"\n";
}
int main()
{
    fastio;
    int T = 1;
    cin>>T;
    for(int csno = 1; csno <= T; csno++)
        solve(csno);

}