#include <bits/stdc++.h>

using namespace std;

const int N = 3030;
const int inf = 0x3f3f3f3f;
const int M = 2e6 + 10;
int head[2 * N], nxt[M], c[M], to[M], e_tot = 1;
int cur[2 * N], dep[2 * N];
int na, nb;
int C[N], a[N], b[N];
int cnta[N], cntb[N];
int visa[N], visb[N];
int S, T;
int pri[500010], vis[2000010], ptot;
int cnt1;

int bfs(int S, int T) {
    for (int i = 0; i <= na + nb + 3; ++i) dep[i] = 0, cur[i] = head[i];
    queue<int> q;
    q.push(S);
    dep[S] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (c[i] && !dep[v]) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[T];
}

int dfs(int u, int T, int lim) {
    if (u == T || !lim) return lim;
    int flow = 0, k;
    for (int i = cur[u]; i && lim; i = nxt[i]) {
        int v = to[i];
        cur[u] = i;
        if (c[i] && dep[v] == dep[u] + 1) {
            k = dfs(v, T, min(lim, c[i]));
            if (!k) dep[v] = 0;
            c[i] -= k, c[i ^ 1] += k;
            flow += k, lim -= k;
        }
    }
    return flow;
}

int dinic(int S, int T) {
    int res = 0;
    while (bfs(S, T)) {
        res += dfs(S, T, inf);
    }
    return res;
}

void add_edge(int x, int y, int w) {
    nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y, c[e_tot] = w;
    nxt[++e_tot] = head[y], head[y] = e_tot, to[e_tot] = x, c[e_tot] = 0;
}

void solve() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &C[i]);
    }
    sort(C + 1, C + n + 1);
    cnt1 = 0;
    for (int i = 1; i <= n; ++i) {
        if (C[i] == 1) ++cnt1;
        else if (C[i] & 1) {
            if (C[i] == a[na]) {
                ++cnta[na];
            }
            else {
                a[++na] = C[i];
                cnta[na] = 1;
            }
        }
        else {
            if (C[i] == b[nb]) {
                ++cntb[nb];
            }
            else {
                b[++nb] = C[i];
                cntb[nb] = 1;
            }
        }
    }
    // int S = na + nb + 1, 
    S = na + nb + 1, T = na + nb + 2;
    for (int i = 1; i <= na; ++i) {
        add_edge(S, i, cnta[i]);
    }
    for (int i = 1; i <= nb; ++i) {
        add_edge(na + i, T, cntb[i]);
    }
    for (int i = 1; i <= na; ++i) {
        for (int j = 1; j <= nb; ++j) {
            if (!vis[a[i] + b[j]]) {
                add_edge(i, na + j, inf);
                visa[i] = visb[j] = 1;
            }
        }
    }
    for (int i = 1; i <= nb; ++i) {
        if (cnt1 && !vis[b[i] + 1]) visb[i] = 1;
    }
    int cnt = 0;
    for (int i = 1; i <= na; ++i) {
        if (visa[i]) cnt += cnta[i];
    }
    for (int i = 1; i <= nb; ++i) {
        if (visb[i]) cnt += cntb[i];
    }
    int vis1 = 0;
    int res1 = dinic(S, T);
    add_edge(S, na + nb + 3, cnt1);
    for (int i = 1; i <= nb; ++i) {
        if (!vis[b[i] + 1]) {
            vis1 = 1;
            add_edge(na + nb + 3, na + i, inf);
        }
    }
    if (cnt1 >= 2) vis1 = 1;
    int res2 = dinic(S, T);
    // cerr << res1 << ' ' << res2 << '\n';
    int ans = 0;
    ans += 2 * (res2 + res1);
    
    ans += (cnt1 - res2) / 2 * 2;
    
    // k -= ans / 2;
    if (k < ans / 2) {
        ans = 2 * k;
        k = 0;
    }
    else k -= ans / 2;
    
    if ((cnt1 - res2) % 2 == 1 && vis1) {
        // &&
        if (k > 0) {
            ++ans;
            --k;
        }
    }
    if (k > 0) {
        cnt -= 2 * res1 + res2;
        // cerr << ans << ' ' << cnt << '\n';
        ans += min(cnt, k);
    }
    printf("%d\n", ans);
    for (int i = 0; i <= e_tot; ++i) {
        to[i] = nxt[i] = c[i] = 0;
    }
    for (int i = 1; i <= na + nb + 3; ++i) {
        head[i] = cur[i] = dep[i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        visa[i] = visb[i] = cnta[i] = cntb[i] = 0;
    }
    na = nb = cnt1 = 0;
    e_tot = 1;
    // if (res2 - res1 >= )
}

int main() {
    for (int i = 2; i <= 2000000; ++i) {
        if (!vis[i]) pri[++ptot] = i;
        for (int j = 1; j <= ptot && i * pri[j] <= 2000000; ++j) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                break;
            }
        }
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}