#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

using namespace std;

int n, k;
vector<int> a;

bool read(){
	if (!(cin >> n >> k))
		return false;
	a.resize(n);
	forn(i, n) cin >> a[i];
	return true;
}

const int N = int(2e6) + 13;

vector<char> isp;

void sieve(){
	isp.resize(N, true);
	fore(i, 2, N){
		if (!isp[i]) continue;
		for (long long j = i * 1ll * i; j < N; j += i)
			isp[j] = false;
	}
	isp[0] = isp[1] = false;
}

vector<int> mt, used;
int T;

bool try_kuhn(int v){
	if (used[v] == T) return false;
	used[v] = T;
	forn(u, n) if (a[u] % 2 == 0 && isp[a[v] + a[u]] && mt[u] == -1){
		mt[u] = v;
		return true;
	}
	forn(u, n) if (a[u] % 2 == 0 && isp[a[v] + a[u]] && mt[u] != -1 && try_kuhn(mt[u])){
		mt[u] = v;
		return true;
	}
	return false;
}

void solve(){
	sort(a.rbegin(), a.rend());
	used.assign(n, 0);
	mt.assign(n, -1);
	int mtsiz = 0;
	int ones = 0;
	T = 1;
	forn(i, n) if (a[i] % 2 == 1){
		if (try_kuhn(i)){
			++T;
			++mtsiz;
		}
		else if (a[i] == 1){
			++ones;
		}
	}
	int tot = 0;
	forn(i, n){
		bool ok = false;
		forn(j, n) if (i != j && isp[a[i] + a[j]])
			ok = true;
		tot += ok;
	}
	mtsiz += ones / 2;
	if (mtsiz >= k){
		cout << k * 2 << '\n';
		return;
	}
	if (mtsiz + (tot - mtsiz * 2) >= k){
		cout << 2 * mtsiz + (k - mtsiz) << '\n';
		return;
	}
	cout << tot << '\n';
}

int main(){
	sieve();
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--){
		read();
		solve();
	}
}