#include <bits/stdc++.h>
int N = 2000000, n, k, cnt = 0, pr[500010], a[3010], deg[3010];
int S, T, now[3010], dep[3010], q[3010];
bool bk[2000010], e[3010][3010], fl[3010];
void init(){
	int i, j;
	for(i = 2; i <= N; i++) bk[i] = true;
	for(i = 2; i <= N; i++){
		if(bk[i]){
			pr[++cnt] = i;
		}
		for(j = 1; j <= cnt && i * pr[j] <= N; j++){
			bk[i * pr[j]] = false;
			if(i % pr[j] == 0) break;
		}
	}
}
int dfs1(int u, int f){
	if(u == T) return f;
	int v, x, res = 0;
	for(v = now[u]; v <= T; v++){
		now[u] = v;
		if(fl[v] && e[u][v] && dep[v] == dep[u] + 1){
			x = dfs1(v, 1);
			if(x > 0){
				e[u][v] = 0; e[v][u] = 1;
				res++; f--;
				if(f == 0) break;
			}
		}
	}
	return res;
}
bool bfs1(){
	int i, u, v, st, nd;
	for(i = 1; i <= T; i++) dep[i] = T + 1, now[i] = 1;
	st = 1; nd = 1; q[1] = S; dep[S] = 0;
	while(st <= nd){
		u = q[st++];
		for(v = 1; v <= T; v++){
			if(fl[v] && dep[v] > T && e[u][v]){
				dep[v] = dep[u] + 1; q[++nd] = v;
			}
		}
	}
	return dep[T] <= T;
}
int dfs2(int u, int f){
	if(u == T) return f;
	int v, x, res = 0;
	for(v = now[u]; v <= T; v++){
		now[u] = v;
		if(e[u][v] && dep[v] == dep[u] + 1){
			x = dfs2(v, 1);
			if(x > 0){
				e[u][v] = 0; e[v][u] = 1;
				res++; f--;
				if(f == 0) break;
			}
		}
	}
	return res;
}
bool bfs2(){
	int i, u, v, st, nd;
	for(i = 1; i <= T; i++) dep[i] = T + 1, now[i] = 1;
	st = 1; nd = 1; q[1] = S; dep[S] = 0;
	while(st <= nd){
		u = q[st++];
		for(v = 1; v <= T; v++){
			if(dep[v] > T && e[u][v]){
				dep[v] = dep[u] + 1; q[++nd] = v;
			}
		}
	}
	return dep[T] <= T;
}
void solve(){
	int i, j, x = 0, y = 0, z = 0, ans = 0, cnt1 = 0;
	scanf("%d%d", &n, &k);
	for(i = 1; i <= n; i++) deg[i] = 0;
	for(i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		if(a[i] == 1) cnt1++;
	}
	for(i = 1; i <= n; i++){
		for(j = 1; j < i; j++){
			e[i][j] = e[j][i] = 0;
			if(bk[a[i] + a[j]]){
				if(a[i] & 1) e[i][j] = 1;
				else e[j][i] = 1;
				deg[i]++; deg[j]++;
			}
		}
		e[i][i] = false; fl[i] = (a[i] > 1);
	}
	for(i = 1; i <= n; i++){
		if(deg[i] > 0) y++;
	}
	S = n + 1; T = n + 2;
	e[S][S] = e[S][T] = e[T][S] = e[T][T] = 0;
	fl[S] = fl[T] = 1;
	for(i = 1; i <= n; i++){
		e[i][S] = e[T][i] = 0;
		e[S][i] = (a[i] & 1);
		e[i][T] = (a[i] & 1 ^ 1);
	}
//	for(i = 1; i <= T; i++){
//		for(j = 1; j <= T; j++){
//			if(e[i][j]) printf("%d %d\n", i, j);
//		}
//	}
	while(bfs1()) x += dfs2(S, n);
	while(bfs2()) z += dfs2(S, n);
//	printf("%d %d %d\n", x, y, z);
	if(k <= x + z) printf("%d\n", k << 1);
	else{
		ans = x + z << 1; k -= x + z;
		if(k << 1 <= cnt1 - z) printf("%d\n", ans + (k << 1));
		else{
			ans += (cnt1 - z >> 1) << 1; k -= cnt1 - z >> 1;
			printf("%d\n", std::min(y, ans + k));
		}
	}
}
int main()
{
	init();
	int t;
	scanf("%d", &t);
	while(t--) solve();
	return 0;
}