#include <bits/stdc++.h>
using namespace std;

int64_t slv(int64_t x) {
    if(x < 5) return 0;
    x -= 5;
    static int c[] = {0, -1, 0};
    return x / 3 + 1 + c[x % 3];
}

const int N = 1e7 + 1, EN = 664579;
int pc, prm[EN];
int spf[N];

auto pre_Sieve = []() {
    for (int i = 2; i < N; i++) {
        if (!spf[i]) spf[i] = prm[pc++] = i;
        for (int j = 0; i * prm[j] < N; j++) {
            spf[i * prm[j]] = prm[j];
            if (spf[i] == prm[j]) break;
        }
    }
    return 0;
}();

void TC() {
    int n;
    int64_t x;
    cin >> n >> x;
    int ans = 0;
    for(int i = 0, y; i < n; i++) {
        cin >> y;
        if(x < 4) {
            ans += y <= x;
            if (x < y) x -= y;
            continue;
        }
        int64_t limit = x / 2;
        if(y <= x) {
            ans++;
            int best = y / 2 + 1;
            if(y < limit) {
                x += y;
            }
            else if(best <= limit)
                x += y % best;
            else
                x += slv(y);
        }
        else {
            x -= spf[y] > limit;
        }
    }
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int tc = 1;
    cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        TC();
    }
    //    cerr << clock() / 1000.0 << " Secs";
    return 0;
}