#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct maxflow {
    struct edge {
        int src, dst, cap, flw;
    };

    vector<edge> edges;
    vector<vector<int>> graph;
    vector<int> first;
    vector<int> dist;

    maxflow(int n) {
        graph.resize(n);
    }

    void bfs(int s) {
        dist.assign(graph.size(), -1);
        dist[s] = 0;
        int h = 0;
        vector<int> q;
        q.push_back(s);
        while (h < q.size()) {
            int x = q[h++];
            for (int i = 0; i < graph[x].size(); i++) {
                edge &e = edges[graph[x][i]];
                if (e.flw == e.cap) continue;
                int y = e.dst;
                if (dist[y] == -1) {
                    dist[y] = dist[x] + 1;
                    q.push_back(y);
                }
            }
        }
    }

    int dfs(int x, int t, int f) {
        if (f == 0) return 0;
        if (x == t) return f;
        for (int i = first[x]; i < graph[x].size(); i++) {
            first[x] = i;
            edge &e = edges[graph[x][i]];
            edge &er = edges[graph[x][i] ^ 1];
            if (e.flw == e.cap || dist[e.dst] != dist[e.src] + 1)
                continue;
            int y = e.dst;
            int res = dfs(y, t, std::min(f, e.cap - e.flw));
            if (res > 0) {
                e.flw += res;
                er.flw -= res;
                return res;
            }
        }
        return 0;
    }

    long maxFlow(int s, int t) {
        long flow = 0;
        while (true) {
            bfs(s);
            first.assign(graph.size(), 0);
            if (dist[t] == -1) break;
            while (true) {
                int pushed = dfs(s, t, INT_MAX);
                if (pushed > 0) {
                    flow += pushed;
                } else {
                    break;
                }
            }
        }
        return flow;
    }

    int addEdge(int u, int v, int cap) {
//    cout << u << " " << v << "\n";
        edges.push_back({u, v, cap, 0});
        edges.push_back({v, u, 0, 0});
        graph[u].push_back(edges.size() - 2);
        graph[v].push_back(edges.size() - 1);
        return edges.size() - 2;
    }
};

const int MAX = 2000001;
vector<bool> prime(MAX, true);

struct test {
    void solve() {
        int n, k;
        cin >> n >> k;
        map<int, int> c0, c1;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x % 2 == 0) {
                c0[x]++;
            } else {
                c1[x]++;
            }
        }
        vector<int> p0, p1;
        for (auto [x, y]: c0) p0.push_back(x);
        for (auto [x, y]: c1) p1.push_back(x);
        int n0 = p0.size();
        int n1 = p1.size();
        maxflow mf(n0 + n1 + 2);
        int s = n0 + n1;
        int t = s + 1;
        for (int i = 0; i < n0; i++) {
            mf.addEdge(s, i, c0[p0[i]]);
        }
        for (int i = 0; i < n1; i++) {
            if (p1[i] != 1) {
                mf.addEdge(n0 + i, t, c1[p1[i]]);
            }
        }
        vector<bool> g0(n0), g1(n1);
        for (int i = 0; i < n0; i++) {
            for (int j = 0; j < n1; j++) {
                if (prime[p0[i] + p1[j]]) {
                    g0[i] = true;
                    g1[j] = true;
                    mf.addEdge(i, n0 + j, n);
                }
            }
        }
        if (c1[1] > 1) {
            g1[0] = true;
        }
        int gn = 0;
        for (int i = 0; i < n0; i++) {
            if (g0[i]) gn += c0[p0[i]];
        }
        for (int i = 0; i < n1; i++) {
            if (g1[i]) gn += c1[p1[i]];
        }
        int r = mf.maxFlow(s, t);

        if (n1 > 0 && p1[0] == 1) {
            int e = mf.addEdge(n0, t, c1[1]);
            r += mf.maxFlow(s, t);
            r += (mf.edges[e].cap - mf.edges[e].flw) / 2;
        }

        //        cout << "! " << r << " " << gn << "\n";
        r = min(r, k);
        int res = min(r * 2 + (k - r), gn);

        cout << res << "\n";
    }
};

int main() {
    ios::sync_with_stdio(false);

    prime[0] = prime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                prime[j] = false;
            }
        }
    }

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }

    return 0;
}