#include <bits/stdc++.h>

template <class T>
struct Flow {
    static constexpr int INF = 1e9;
    int n;
    struct Edge {
        int to;
        T cap;
        Edge(int to, T cap) : to(to), cap(cap) {}
    };
    std::vector<Edge> edge;
    std::vector<std::vector<int>> adj;
    std::vector<int> cur, dep;
    explicit Flow(int n) : n(n), adj(n) {}
    bool bfs(int s, int t) {
        dep.assign(n, -1);
        std::queue<int> q;
        dep[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int i : adj[node]) {
                int to = edge[i].to;
                T c = edge[i].cap;
                if (c > 0 && dep[to] == -1) {
                    dep[to] = dep[node] + 1;
                    if (to == t) {
                        return true;
                    }
                    q.push(to);
                }
            }
        }
        return false;
    }
    T dfs(int node, int t, T flow) {
        if (node == t || flow == 0) {
            return flow;
        }
        T f, res = 0;
        for (int &i = cur[node]; i < int(adj[node].size()); ++i) {
            int j = adj[node][i];
            int to = edge[j].to;
            T c = edge[j].cap;

            if (dep[to] == dep[node] + 1 && 
                (f = dfs(to, t, std::min(flow, c)))) {
                res += f;
                flow -= f;
                edge[j].cap -= f;
                edge[j ^ 1].cap += f;
            }

            if (flow == 0) {
                break;
            }
        }
        if (!res) {
            dep[node] = -1;
        }
        return res;
    }
    int add_edge(int u, int v, T c) {
        int j = edge.size();
        adj[u].push_back(edge.size());
        edge.emplace_back(v, c);
        adj[v].push_back(edge.size());
        edge.emplace_back(u, 0);
        return j;
    }
    T operator()(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, INF);
        }
        return ans;
    }
};

constexpr int N = 2e6 + 19;

bool vist[N];
int prime[N], pcnt;

bool has_friend[N];
void solve() {
    int n, k;
    std::cin >> n >> k;

    std::map<int, int> count;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        count[x] += 1;
    }
    int c1 = count[1], e1 = 0;
    count[1] = 0;

    std::array<std::vector<int>, 2> a;
    for (auto [x, c] : count) {
        a[x & 1].push_back(x);
    }

    Flow<int> f(a[0].size() + a[1].size() + 2);
    const int s = f.n - 1, t = f.n - 2;

    for (int x = 0; x < a[0].size(); ++x) {
        f.add_edge(s, x, count[a[0][x]]);
    }
    for (int y = 0; y < a[1].size(); ++y) {
        int j = f.add_edge(a[0].size() + y, t, count[a[1][y]]);
        if (a[1][y] == 1) {
            e1 = j;
        }
    }
    for (int x = 0; x < a[0].size(); ++x) {
        for (int y = 0; y < a[1].size(); ++y) {
            if (!vist[a[0][x] + a[1][y]]) {
                f.add_edge(x, a[0].size() + y, Flow<int>::INF);
                if (a[1][y] != 1 || c1) {
                    has_friend[a[0][x]] = true;
                    has_friend[a[1][y]] = true;
                }
            }
        }
    }
    if (c1 >= 2) {
        has_friend[1] = true;
    }

    int matching = f(s, t);
    count[1] = c1;
    f.edge[e1].cap += c1;
    matching += f(s, t);
    matching += f.edge[e1].cap / 2;

    int tot = 0;
    for (auto [x, c] : count) {
        if (has_friend[x]) {
            tot += c;
        }
        has_friend[x] = false;
    }

    if (k <= matching) {
        std::cout << k * 2 << '\n';
    } else {
        int ans = matching * 2 + (k - matching);
        ans = std::min(ans, tot);
        std::cout << ans << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    for (int i = 2; i < N; ++i) {
        if (!vist[i]) {
            prime[++pcnt] = i;
        }
        for (int j = 1; j <= pcnt && i * prime[j] < N; ++j) {
            vist[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    
    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }
}