#include <bits/stdc++.h>

#define ff first
#define ss second
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;

struct edge { int v, cap, inv, flow; };
struct network {
	int n, s, t; 
	vector<int> lvl;
	vector<vector<edge>> g;

	network(int n_): n(n_), lvl(n_), g(n_) {}
	void add_edge(int u, int v, int c) {
		g[u].pb({v, c, (int)g[v].size(), 0});
		g[v].push_back({u, 0, (int)g[u].size()-1, c});
	}

	bool bfs() {
		fill(lvl.begin(), lvl.end(), -1);
		queue <int> q;
		lvl[s] = 0;
		for (q.push(s); q.size(); q.pop()) {
			int u = q.front();
			for (auto& e : g[u]) {
				if (e.cap > 0 && lvl[e.v] == -1) {
					lvl[e.v] = lvl[u] + 1;
					q.push(e.v);
				}
			}
		}

		return lvl[t] != -1;
	}

	int dfs(int u, int nf) {
		if (u == t) return nf;
		int res = 0;
		for (auto& e : g[u]) {
			if (e.cap >0 && lvl[e.v] == lvl[u] + 1) {
				int tf = dfs(e.v, min(nf, e.cap));
				res += tf; nf -= tf; e.cap -= tf;
				g[e.v][e.inv].cap += tf;
				g[e.v][e.inv].flow -= tf;
				e.flow += tf;
				if (nf == 0) return res;
			}
		}

		if (!res) lvl[u] = -1;
		return res;
	}

	int max_flow(int so, int si, int res = 0) {
		s = so; t = si;
		while (bfs()) res += dfs(s, INT_MAX);
		return res;
	}
};

const int maxn = 2e6 + 5;
bool sieve[maxn];

int main(){
	#ifdef LOCAL
		freopen("in","r", stdin);
		freopen("out","w",stdout);
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0);

	sieve[0] = sieve[1] = 1;
	for (int i=2; i<maxn; ++i) {
		for (int j = i+i; j<maxn; j += i) sieve[j] = 1;
	}

	int tt; cin >> tt;
	while (tt--) {
		int n, k; cin >> n >> k;
		vector<int> a(n); 
		for (int i=0; i<n; ++i) cin >> a[i];

		sort(a.begin(), a.end());
		vector<pair<int, int>> b;
		for (int i=0, j=0; i<n; i=j) {
			while (j<n && a[i] == a[j]) ++j;
			b.pb({a[i], j - i});
		}

		int m = b.size(), ones = 0;
		vector<bool> good(m, 0);

		int s = m, t = m+1;
		network net(m+3);
		for (int i = 0; i<m; ++i) {
			int ai = b[i].ff, c = b[i].ss;
			if (ai == 1) { ones = c; continue; }

			if (ai&1) net.add_edge(i, t, c);
			else {
				net.add_edge(s, i, c);

				for (int j=0; j<m; ++j) {
					int aj = b[j].ff;
					if (!sieve[ai + aj]) {

						net.add_edge(i, j, INT_MAX);
						good[i] = good[j] = 1;
					}
				}
			}
		}


		auto solve = [&](int& flow, int rem) -> int {
			flow = net.max_flow(s, t, flow);

			int total = flow + (rem / 2);
			if(total >= k) return 2*k;

			int ans = 2*total;
			for(edge& e : net.g[s]) if (good[e.v]) {
				int mn = min(k - total, e.cap);
				total += mn, ans += mn;
			}

			for (edge& e : net.g[t]) if (good[e.v]) {
				int mn = min(k - total, e.flow);
				total += mn, ans += mn;
			}

			int mn = min(rem%2, k - total);
			if (good[0] || (rem > 1 || ones > rem)) total += mn, ans += mn;

			return ans;
		};

		int flow = 0;	
		int ans = solve(flow, ones);
		for (int i=1; i<=ones; ++i) {
			net.add_edge(0, t, 1);
			ans = max(ans, solve(flow, ones - i));
		}

		cout << ans << '\n';
	}
	return 0;
}