#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3010, M = 1e7 + 10, INF = 0x3f3f3f3f, mod = 998244353;

namespace MF {
    const int INF = 1e8;
    int S, T = N - 1;
    int h[N], e[M], f[M], ne[M], idx;
    int q[N], d[N], cur[N];
    void clear() {
        memset(h, -1, sizeof h), idx = 0;
    }
    void add_edge(int a, int b, int c) {
        // cout << a << ' ' << b << ' ' << c << el;
        e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
        e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
    }
    bool bfs() {
        int hh = 0, tt = 0;
        memset(d, -1, sizeof d);
        q[0] = S, d[S] = 0, cur[S] = h[S];
        while (hh <= tt) {
            int t = q[hh++];
            for (int i = h[t]; ~i; i = ne[i]) {
                int ver = e[i];
                if (d[ver] == -1 && f[i]) {
                    d[ver] = d[t] + 1;
                    cur[ver] = h[ver];
                    if (ver == T) return 1;
                    q[++tt] = ver;
                }
            }
        }
        return 0;
    }
    int find(int u, int limit) {
        if (u == T) return limit;
        int flow = 0;
        for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
            cur[u] = i;
            int ver = e[i];
            if (d[ver] == d[u] + 1 && f[i]) {
                int t = find(ver, min(f[i], limit - flow));
                if (!t) d[ver] = -1;
                f[i] -= t, f[i ^ 1] += t, flow += t;
            }
        }
        return flow;
    }
    int dinic() {
        int r = 0, flow;
        while (bfs()) while (flow = find(S, INF)) r += flow;
        return r;
    }
}

int primes[2000010], idx;
bool st[2000010];

// 线性筛质数
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) primes[idx++] = i;
        for (int j = 0; primes[j] <= n / i; ++j) {
            st[i * primes[j]] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

void solve() {
    MF::clear();
    int n, k; cin >> n >> k;
    int one = 0;
    vector<int> a(n + 1);
    MF::add_edge(MF::S, N - 2, 0);
    map<int, int> odd, even;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] == 1) ++one;
        else {
            if (a[i] & 1) ++odd[a[i]];
            else ++even[a[i]];
        }
    }
    int valid = 0;
    for (int i = 1; i <= n; ++i) {
        int t = 0;
        for (int j = 1; j <= n; ++j) 
            if (i != j && !st[a[i] + a[j]]) {
                t = 1; break;
            }
        valid += t;
    }
    int tot = 0;
    map<int, int> mp;
    for (auto[a, b]: odd) {
        mp[a] = ++tot;
        MF::add_edge(MF::S, tot, b);
    }
    for (auto[a, b]: even) {
        mp[a] = ++tot;
        MF::add_edge(tot, MF::T, b);
        if (!st[1 + a]) MF::add_edge(N - 2, tot, b);
    }
    for (auto[a, b]: odd) for (auto[c, d]: even) {
        if (!st[a + c]) MF::add_edge(mp[a], mp[c], b + d);
    }
    int two = MF::dinic();
    for (int i = 1; i <= one; ++i) {
        ++MF::f[0];
        int t = MF::dinic();
        assert(t <= 1);
        if (t) ++two;
        else {
            two += (one - i + 1) / 2;
            break;
        }
    }
    two = min(two, k);
    cout << min(two * 2 + (k - two), valid) << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    sieve(2e6);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}