// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return b < a ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 3005;
const int MAXA = 2000005;

template <class T = int, int PW = 0>
struct FlowGraph {
    struct edge {
        int v;
        T cap, flow;
        int rid;
    };
    int n;
    T lim;
    T inf;
    vector<vector<edge>> adj;
    vector<int> dist, ptr;
    FlowGraph(): n(0), inf(0) {}
    FlowGraph(int n): n(n), inf(0) {
        dist.resize(n, -1);
        ptr.resize(n, 0);
        adj.resize(n);
    }
    void add_edge(int u, int v, T cap = 1, T rcap = 0) {
        int id = adj[u].size(), rid = adj[v].size();
        adj[u].push_back((edge) {v, cap, 0, rid});
        adj[v].push_back((edge) {u, rcap, 0, id});
        inf = max(inf, max(cap, rcap) + 5);
    }
    bool bfs(int src, int sink) {
        for (int i = 0; i < n; i++) {
            dist[i] = -1;
        }
        queue<int> q;
        dist[src] = 0;
        q.push(src);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (edge e : adj[u]) {
                if (e.cap - e.flow < lim) continue;
                if (dist[e.v] != -1) continue;
                dist[e.v] = dist[u] + 1;
                q.push(e.v);
            }
        }
        return dist[sink] != -1;
    }
    T dfs(int u, int sink, T flow) {
        if (u == sink) return flow;
        for (; ptr[u] < adj[u].size(); ptr[u]++) {
            edge &e = adj[u][ptr[u]];
            if (dist[u] + 1 != dist[e.v]) continue;
            if (e.cap - e.flow < lim) continue;
            T cflow = min(flow, e.cap - e.flow);
            cflow = dfs(e.v, sink, cflow);
            if (cflow) {
                e.flow += cflow;
                adj[e.v][e.rid].flow -= cflow;
                return cflow;
            }
        }
        return 0;
    }
    T flow(int src, int sink) {
        T res = 0;
        for (lim = ((T) 1 << PW); lim > 0; lim >>= 1) {
            while (bfs(src, sink)) {
                for (int i = 0; i < n; i++) {
                    ptr[i] = 0;
                }
                while (T cflow = dfs(src, sink, inf)) {
                    res += cflow;
                }
            }
        }
        return res;
    }
    bool leftCut(int x) {
        return dist[x] != -1;
    }
};

bool isp[MAXA];
int t;
int n, k;
int a[MAXN];
bool avail[MAXN];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    REP (i, 2, MAXA) {
        isp[i] = 1;
    }
    for (int i = 2; i * i < MAXA; i++) {
        if (!isp[i]) {
            continue;
        }
        for (int j = i * i; j < MAXA; j += i) {
            isp[j] = 0;
        }
    }
    cin >> t;
    while (t--) {
        cin >> n >> k;
        FlowGraph fg(n + 2);
        int src = n, sink = n + 1;
        int ans = 0, ocnt = 0;
        vi vone;
        REP (i, 0, n) {
            cin >> a[i];
            if (a[i] == 1) {
                ocnt++;
                vone.pb(i);
            }
        }
        REP (i, 0, n) {
            avail[i] = 0;
            REP (j, 0, n) {
                if (i == j) {
                    continue;
                }
                avail[i] |= isp[a[i] + a[j]];
            }
        }
        REP (i, 0, n) {
            if (a[i] == 1) {
                a[i] = 0;
            }
        }
        REP (i, 0, n) {
            if (a[i] == 0) {
                continue;
            }
            if (a[i] % 2 == 0) {
                fg.add_edge(i, sink);
            } else {
                fg.add_edge(src, i);
            }
        }
        REP (i, 0, n) {
            if (a[i] == 0) {
                continue;
            }
            REP (j, 0, n) {
                if (a[j] == 0) {
                    continue;
                }
                if (a[j] % 2 == 1) {
                    continue;
                }
                if (isp[a[i] + a[j]]) {
                    fg.add_edge(i, j);
                }
            }
        }
        int flow = fg.flow(src, sink);
        //cerr << flow << '\n';
        int mn = min(flow, k);
        k -= mn;
        int base = mn * 2;
        REP (ones, 0, ocnt + 1) {
            int extra = 0;
            REP (i, 0, n) {
                if (a[i] == 0) {
                    continue;
                }
                bool filled = fg.adj[i][0].flow != 0;
                //cerr << ' ' << i << ' ' << filled << '\n';
                if (filled) {
                    continue;
                }
                if (avail[i]) {
                    extra++;
                }
            }
            int res = base;
            int tk = k;
            int mn = min(tk, (ocnt - ones) / 2);
            tk -= mn;
            res += mn * 2;
            res += min(tk, extra);
            mxto(ans, res);
            if (ones == ocnt) {
                break;
            }
            int i = vone.back(); vone.pop_back();
            a[i] = 1;
            fg.add_edge(src, i);
            REP (j, 0, n) {
                if (a[j] % 2 == 1) {
                    continue;
                }
                if (isp[a[i] + a[j]]) {
                    fg.add_edge(i, j);
                }
            }
            int flow = fg.flow(src, sink);
            //cerr << flow << '\n';
            mn = min(flow, k);
            k -= mn;
            base += mn * 2;
        }
        cout << ans << '\n';
    }
    return 0;
}