#include <cstdio>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <cctype>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>

namespace uvu
{
#define LOCAL ________________DONT_DEFINE_ME_______________
#define ll long long
#define inf 0x3f3f3f3f
// #define int long long
// #define inf 0x3f3f3f3f3f3f3f3fll
#define infll 0x3f3f3f3f3f3f3f3fll
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define gline debug("now is #%d\n", __LINE__)
#define pii std::pair <int, int>
#define mkp std::make_pair
#define fi first
#define se second
char _ST_;
const int BUFSIZE = (1 << 20);
char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf;
char obuf[BUFSIZE], *oS = obuf, *oT = obuf + BUFSIZE;
char getc()
{
#ifdef LOCAL
	return getchar();
#else
	if(iS == iT) iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
	return (iS == iT) ? EOF : *iS++;
#endif
#define getchar ERR
}
void Flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; }
struct Flusher { ~Flusher() { Flush(); } }iamflusher;
void putc(char c)
{
#ifdef LOCAL
	putchar(c);
#else
	*oS++ = c;
	if(oS == oT) Flush();
#endif
}
template <typename T = int> T read()
{
	T x = 0, f = 1; char c = getc();
	for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
	for(;  isdigit(c); c = getc()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}
template <typename T> void print(T x, char c)
{
static int sta[BUFSIZE], top;
	top = 0;
	if(x < 0) putc('-'), x *= -1;
	if(!x) sta[++top] = 0;
	for(; x; x /= 10) sta[++top] = x % 10;
	for(; top; putc(sta[top--] ^ 48));
	if(c) putc(c);
}
int readstr(char *s, int base)
{
	int idx = base - 1; char c = getc();
	for(; !(isdigit(c) || isalpha(c) || c == '#' || c == '.'); c = getc());
	for(;   isdigit(c) || isalpha(c) || c == '#' || c == '.' ; c = getc()) s[++idx] = c;
	return idx - base + 1;
}
void printf(const char *s) { for(; *s; s++) putc(*s); }
template <typename T, typename ... Args >
void printf(const char *s, T x, Args ... rest)
{
	for(; *s; s++)
	{
		if(*s != '%') { putc(*s); continue; }
		s++; if(*s == 'd') print(x, 0);
		else if(*s == 'c') putc(x);
		printf(s + 1, rest ...);
		return;
	}
}
template <typename T> void ckmin(T &x, T y) { x = x < y ? x : y; }
template <typename T> void ckmax(T &x, T y) { x = x > y ? x : y; }
#define mod 998244353
// #define mod 1000000007
int sm(int x) { return x >= mod ? x - mod : x; }
void plus_(int &x, int y) { x = sm(x + y); }
void mul_(int &x, int y) { x = 1ll * x * y % mod; }
int ksm(int a, int b) { int res = 1; for(; b; b >>= 1, mul_(a, a)) if(b & 1) mul_(res, a); return res; }

#define N 3010
#define M 2260010
int n, m, S, T;
int h[N], e[M << 1], ne[M << 1], f[M << 1], idx = -1;
void add_edge(int x, int y, int z) { ne[++idx] = h[x], h[x] = idx, e[idx] = y, f[idx] = z; }
void add(int x, int y, int z) { /* printf("add(%d %d %d)\n", x, y, z); */ add_edge(x, y, z), add_edge(y, x, 0); }
int ceng[N], cur[N], q[N], head, tail;
bool bfs()
{
	for(int i = S; i <= T; i++) ceng[i] = -1, cur[i] = h[i];
	ceng[q[head = tail = 1] = S] = 0;
	for(int k, nx; head <= tail; ) for(int i = h[k = q[head++]]; ~i; i = ne[i]) if(f[i] && !~ceng[nx = e[i]]) ceng[q[++tail] = nx] = ceng[k] + 1;
	return ~ceng[T];
}

int dfs(int k, int flow)
{
	if(k == T) return flow;
	int res = 0; for(int i = cur[k]; ~i && res < flow; i = cur[k] = ne[i])
	{
		int nx = e[i];
		if(f[i] && ceng[nx] == ceng[k] + 1)
		{
			int t = dfs(nx, std::min(flow - res, f[i]));
			f[i] -= t, f[i ^ 1] += t, res += t;
		}
	}
	return res;
}

int dinic() { int res = 0, x; while(bfs()) while((x = dfs(S, inf))) res += x; return res; }
int a[N], sta[N], top;
#define P 2000010
int prime[P], pidx; bool vis[P]; 
int tag[N], ans;
void paint(int k, int &m)
{
	// printf("paint %d\n", k);
	if(!m) return;
	ceng[k] = 1;
	if(!tag[k]) m--, ans++;//, printf("[k = %d]\n", k);
	if(!m) return;
	for(int i = 1; i <= n; i++) if(!~ceng[i] && !vis[a[i] + a[k]]) 
	{
		paint(i, m);//, printf("%d -> %d\n", i, k);
		if(!m) return;
	}
}

void solve()
{
	// memset(h, idx = -1, sizeof(h)); 
	n = read(), m = read();
	for(int i = 0; i <= n + 1; i++) h[i] = idx = -1;
	int tot = 0; top = 0;
	for(int i = 1; i <= n; i++)
	{
		a[i] = read();
		if(a[i] == 1) tot++;
		else sta[++top] = a[i];
	}
	ans = 0;
	// ans = tot / 2; if(tot & 1) sta[++top] = tot & 1, tot--;
	/* n = top; */ 
	for(int i = 1; i <= n; i++) tag[i] = 0;
	for(int i = 1; i <= top; i++) a[i] = sta[i];
	S = 0; T = n + 1;
	for(int i = 1; i <= top; i++) 
	{
		// printf("a[%d] = %d\n", i, a[i]);
		if(a[i] & 1)
		{
			add(S, i, 1);
			for(int j = 1; j <= top; j++) if(!vis[a[i] + a[j]])
				add(i, j, 1);
		}
		else add(i, T, 1);
	}
	// debug("idx = %d\n", idx);
	ans += dinic();
	for(int i = top + 1; i <= n; i++)
	{
		a[i] = 1;
		add(S, i, 1);
			for(int j = 1; j <= top; j++) if(!vis[a[i] + a[j]])
				add(i, j, 1);
	}
	// debug("ans = %d\n", ans);
	ans += dinic();
	// debug("ans = %d\n", ans);
	// for(int i = 1; i <= n; i++) printf("a[%d] = %d\n", i, a[i]);
	for(int i = h[S]; ~i; i = ne[i]) if(!f[i]) tag[e[i]] = 1;//, printf("tagA[%d] = 1\n", e[i]);
	for(int i = h[T]; ~i; i = ne[i]) if(f[i]) tag[e[i]] = 1;//, printf("tagB[%d] = 1\n", e[i]);
	for(int i = 1, lst = 0; i <= n; i++) if(!tag[i] && a[i] == 1)
	{
		if(!lst) lst = i;
		else
			tag[i] = tag[lst] = 1, ans++, lst = 0;
	}
	if(ans >= m) { print(m * 2, '\n'); return; }
	m -= ans; ans *= 2;
	for(int i = 1; i <= n; i++) ceng[i] = -1;
	// for(int i = 1; i <= n; i++) printf("tag[%d] = %d\n", i, tag[i]);
	for(int i = 1; i <= n; i++) if(tag[i] && !~ceng[i] && m) paint(i, m);
	print(ans, '\n');
}

void init()
{
	int n = P - 10;
	vis[1] = 1;
	for(int i = 2; i <= n; i++) 
	{
		if(!vis[i]) prime[++pidx] = i;
		for(int j = 1; j <= pidx && i * prime[j] <= n; j++)
		{
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
char _ED_;
void mian()
{
	debug("%.3f MB\n", abs(&_ST_ - &_ED_) / 1024.0 / 1024);
	init();
	int T = read();
	for(; T; solve(), T--);
}
#ifdef int
	#undef int
#endif
}

int main()
{
	uvu::mian(); return 0;
}