#include<bits/stdc++.h>
using namespace std;
const int MAXN=3100,MAXM=2e6+1;
int T,n,k;
int a[MAXN],f[MAXM],ru[MAXN],id[MAXN],vis[MAXN];
vector<int> p[MAXN];
bool cmp(int x, int y) {
  return ru[x]<ru[y];
}
void solve() {
  cin >> n >> k;
  for (int i=1; i<=n; i++) {
    cin >> a[i];
    id[i]=i;
    vis[i]=0;
    p[i].clear();
    ru[i]=0;
  }
  for (int i=1; i<=n; i++) {
    for (int j=i+1; j<=n; j++) {
      if (!f[a[i]+a[j]]) {
        p[i].push_back(j);
        p[j].push_back(i);
        ru[i]++,ru[j]++;
      }
    }
  }
  sort(id+1,id+n+1,cmp);
  int ans=0,sum=0;
  for (int x=1; x<=n; x++) {
      int i=id[x];
      if (!k) {
        break;
      }
      if (p[i].empty() || vis[i]) {
        continue;
      }
      int min1=1e9,min2=0;
      for (int v : p[i]) {
        if (!vis[v] && ru[v]<min1) {
          min1=ru[i];
          min2=v;
        }
      }
      if (!min2) {
        vis[i]=1;
        for (int v : p[i]) {
          ru[v]--;
        }
        sum++;
        continue;
      }
      vis[i]=vis[min2]=1;
      for (int v : p[i]) {
        ru[v]--;
      }
      for (int v : p[min2]) {
        ru[v]--;
      }
      ans+=2;
      k--;
  }
  //cout<< ans << " " << sum << " " << k << "\n";
  ans+=min(k,sum);
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0);
  cin >> T;
  f[1]=1;
  for (int i=2; i<MAXM; i++) {
      if (!f[i]) {
        for (int j=i*2; j<MAXM; j+=i) {
          f[j]=1;
        }
      }
  }
  while (T--) {
    solve();
  }
  return 0;
}