#include <cstdio>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 3e3 + 50;
const int M = 2e6 + 500;

int comp[M], na, nb, uzeoA[N], uzeoB[N];
vector < vi > g;
vector < int > btoa;
int AA[N], BB[N];

bool dfs(int a, int L) {
	if (AA[a] != L) return 0;
	AA[a] = -1;
	for (int b : g[a]) if (BB[b] == L + 1) {
		BB[b] = 0;
		if (btoa[b] == -1 || dfs(btoa[b], L + 1)) {
			return btoa[b] = a, 1;
		}
	}
	return 0;
}

int hopcroftKarp() {
	int res = 0;
	int na = (int)g.size();
	vi cur, next;
	for (;;) {
		fill(AA, AA + na, 0);
		fill(BB, BB + nb, 0);
		cur.clear();
		for(int a : btoa) if(a != -1) AA[a] = -1;
		for(int a = 0;a < na;a++) if(AA[a] == 0) cur.PB(a);
		for (int lay = 1;;lay++) {
			bool islast = 0;
			next.clear();
			for (int a : cur) for (int b : g[a]) {
				if(btoa[b] == -1) {
					BB[b] = lay;
					islast = 1;
				} else if(btoa[b] != a && !BB[b]) {
					BB[b] = lay;
					next.push_back(btoa[b]);
				}
			}
			if(islast) break;
			if (next.empty()) return res;
			for (int a : next) AA[a] = lay;
			cur.swap(next);
		}
		for(int a = 0;a < na;a++)
			res += dfs(a, 0);
	}
}

int A[N], B[N];

void precompute() {
	comp[1] = 1;
	for(int i = 2;i < M;i++) {
		if(comp[i]) continue;
		for(int j = 2 * i;j < M;j += i)
			comp[j] = 1;
	}
}

void solve() {
	int n, k; scanf("%d%d", &n, &k);
	na = 0, nb = 0;
	int jen = 0;
	for(int i = 0;i < n;i++) {
		int x; scanf("%d", &x);
		jen += (x == 1);
		if(x & 1) uzeoA[na] = 0, A[na++] = x;
		else uzeoB[nb] = 0, B[nb++] = x;
	}
	g.clear();
	btoa.clear();
	btoa.resize(nb);
	fill(btoa.begin(), btoa.end(), -1);
	sort(A, A + na); reverse(A, A + na);
	for(int i = 0;i < na;i++) {
		if(A[i] == 1) break;
		vi tmp;
		for(int j = 0;j < nb;j++) {
			if(!comp[A[i] + B[j]]) uzeoA[i] = 1, uzeoB[j] = 1, tmp.PB(j);
		}
		g.PB(tmp);
	}
	int old_ans = hopcroftKarp();
	int start = 0;
	while(start < na && A[start] != 1) start++;
	if(na - start > 1) {
		for(int i = 0;i < na;i++) if(A[i] == 1) uzeoA[i] = 1;
	}
	for(int i = start;i < na;i++) {
		vi tmp;
		for(int j = 0;j < nb;j++) {
			if(!comp[A[i] + B[j]]) uzeoA[i] = 1, uzeoB[j] = 1, tmp.PB(j);
		}
		g.PB(tmp);
	}
	int max_ans = 0;
	for(int i = 0;i < na;i++) max_ans += uzeoA[i];
	for(int i = 0;i < nb;i++) max_ans += uzeoB[i];
	for(int &y : btoa) y = -1;	
	int new_ans = hopcroftKarp();
	int mm = new_ans + (jen - (new_ans - old_ans)) / 2;
	if(k <= mm) printf("%d\n", 2 * k);
	else printf("%d\n", min(max_ans, k + mm));
}

int main() {
	precompute();
	int T; scanf("%d", &T);
	for(;T--;) solve();
	return 0;
}