#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

bool Mst;

const int maxn = 3030;
const int maxm = 2000100;
const int N = 2000000;

int n, m, a[maxn], b[maxn], tot, pr[maxm / 10], K;
bitset<maxm> vis;

inline void init() {
	vis[0] = vis[1] = 1;
	for (int i = 2; i <= N; ++i) {
		if (!vis[i]) {
			pr[++tot] = i;
		}
		for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
			vis[i * pr[j]] = 1;
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
}

int id[maxn], S, T, nt, hd[maxn * 10], len;

struct edge {
	int next;
	short to, cap;
} edges[4600000];

inline void add_edge(int u, int v, int c) {
	edges[++len].to = v;
	edges[len].next = hd[u];
	edges[len].cap = c;
	hd[u] = len;
}

struct Dinic {
	int d[maxn * 10], cur[maxn * 10];
	bool vis[maxn * 10];
	
	inline void add(int u, int v, int c) {
		add_edge(u, v, c);
		add_edge(v, u, 0);
	}
	
	inline bool bfs() {
		queue<int> q;
		for (int i = 1; i <= nt; ++i) {
			vis[i] = 0;
			d[i] = -1;
		}
		q.push(S);
		vis[S] = 1;
		d[S] = 0;
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int i = hd[u]; i; i = edges[i].next) {
				edge &e = edges[i];
				if (!vis[e.to] && e.cap) {
					vis[e.to] = 1;
					d[e.to] = d[u] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[T];
	}
	
	short dfs(int u, short a) {
		if (u == T || !a) {
			return a;
		}
		short flow = 0, f;
		for (int &i = cur[u]; i; i = edges[i].next) {
			edge &e = edges[i];
			if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap))) > 0) {
				e.cap -= f;
				edges[i ^ 1].cap += f;
				flow += f;
				a -= f;
				if (!a) {
					break;
				}
			}
		}
		return flow;
	}
	
	inline int solve() {
		int flow = 0;
		while (bfs()) {
			for (int i = 1; i <= nt; ++i) {
				cur[i] = hd[i];
			}
			flow += dfs(S, 15000);
		}
		return flow;
	}
} solver;

void solve() {
	for (int i = 0; i <= nt; ++i) {
		hd[i] = 0;
	}
	nt = 0;
	len = 1;
	S = ++nt;
	T = ++nt;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	K = 0;
	for (int i = 1; i <= n; ++i) {
		bool fl = 0;
		for (int j = 1; j <= n && !fl; ++j) {
			fl |= (i != j && !vis[a[i] + a[j]]);
		}
		if (fl) {
			b[++K] = a[i];
		}
	}
	for (int i = 1; i <= K; ++i) {
		id[i] = ++nt;
		if (b[i] == 1) {
			continue;
		}
		if (b[i] & 1) {
			solver.add(S, id[i], 1);
		} else {
			solver.add(id[i], T, 1);
		}
	}
	for (int i = 1; i <= K; ++i) {
		if (b[i] % 2 == 0) {
			continue;
		}
		for (int j = 1; j <= K; ++j) {
			if (b[j] % 2 == 0 && !vis[b[i] + b[j]]) {
				solver.add(id[i], id[j], 1);
			}
		}
	}
	int flow = solver.solve();
	for (int i = hd[S]; i; i = edges[i].next) {
		edges[i].cap = edges[i ^ 1].cap = 0;
	}
	int cnt = 0;
	for (int i = 1; i <= K; ++i) {
		if (b[i] == 1) {
			solver.add(S, id[i], 1);
			++cnt;
		}
	}
	int t = solver.solve();
	flow += t + (cnt - t) / 2;
	if (flow >= m) {
		printf("%d\n", m * 2);
		return;
	}
	printf("%d\n", min(K, flow * 2 + m - flow));
}

bool Med;

int main() {
	fprintf(stderr, "%.2lf MB\n", (&Mst - &Med) / 1048576.);
	init();
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}