#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

#define N 3010
#define M 2000010

bool vst[M];
vector<int>pri;

int n, a[N], k;
int id[M], num[M];
int S, T;
int k1, k2;
struct edge
{
    int nxt, to, fl;
}e[M << 1];
int h[N], cur[N], cnt = 1;
int dep[N];
int n0;

void pre(int n)
{
    for (int i = 2; i <= n; i ++)
    {
        if (!vst[i]) pri.push_back(i);
        for (int x : pri)
        {
            if (1LL * x * i > n) break;
            vst[x * i] = 1;
            if (i % x == 0) break;
        }
    }
}


void add(int u, int v, int fl)
{
    e[++ cnt] = (edge) {h[u], v, fl}; h[u] = cnt;
    e[++ cnt] = (edge) {h[v], u, +0}; h[v] = cnt;
}
bool bfs()
{
    for (int i = 1; i <= T; i ++)dep[i] = 0, cur[i] = h[i];
    queue<int>q; dep[S] = 1; q.push(S);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = h[u]; i; i = e[i].nxt) if (e[i].fl)
        {
            int v = e[i].to; if (dep[v])continue;
            dep[v] = dep[u] + 1; q.push(v);
            if (v == T)return 1;
        }
    }
    return 0;
}
int dfs(int u, int flow)
{
    if (u == T)return flow;
    int res = 0;
    for (int &i = cur[u]; i; i = e[i].nxt) 
    {
        int v = e[i].to;
        if (dep[v] != dep[u] + 1 || (!e[i].fl))continue;
        int fl = dfs(v, min(flow - res, e[i].fl));
        res += fl;
        e[i].fl -= fl;
        e[i ^ 1].fl += fl;
        if (res == flow) return res;
    }
    if (!dep[u]) dep[u] = 0;
    return res;
}
int Dinic()
{
    int sum = 0;
    while (bfs()) sum += dfs(S, 1e9);
    return sum; 
}

void sol()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    vector<int>A, B;
    for (int i = 1; i <= n; i ++) if (!id[a[i]]) 
    {
        id[a[i]] = ++ n0;
        if (a[i] % 2 == 1)A.push_back(a[i]);
        else B.push_back(a[i]);
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++) if (i != j)
        {
            if (!vst[a[i] + a[j]]) {k1 ++; break;}
        }
    }
    for (int i = 1; i <= n; i ++)num[a[i]] ++;
    S = n0 + 1, T = n0 + 2;
    for (int x : A) if(x != 1)add(S, id[x], num[x]);
    for (int y : B) add(id[y], T, num[y]);
    for (int x : A) for (int y : B) if (!vst[x + y])
    {
        // cout << "??:" << x << ' ' << y << endl;
        add(id[x], id[y], 1e9);
    }


    // cout << "???:" << k1 << ' ' << k2 << " " << num[1] << endl;
    k2 = Dinic(); k1 -= 2 * k2;

    // cout << "EE:" << k1 << ' ' << k2 << endl;

    // cout << "GG:" << endl;
    while (num[1])
    {
        add(S, id[1], 1);
        int w = Dinic();
        if (w) {k2 ++; k1 -= 2; num[1] --;}
        else break;
    }
    k2 += (num[1] / 2);
    k1 -= (num[1] / 2) * 2;

    if (k <= k2) {cout << 2 * k << '\n';}
    else {cout << 2 * k2 + min(k1, k - k2) << '\n';}

    // cout << "EE:" << T << endl;

    for (int i = 1; i <= T; i ++)h[i] = cur[i] = dep[i] = 0;
    for (int i = 1; i <= n; i ++) num[a[i]] = id[a[i]] = 0;
    k1 = k2 = 0; cnt = 1; n0 = S = T = 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    pre(M - 10);
    int T = 1;
    cin >> T;
    while (T --) sol();
    return 0;
}
/*
1
5 3
3 4 12 3 6
*/