#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (int i = (s); i < (int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (int i = (int)(s - 1); i >= (int)(e); i--)
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T, typename U>
T chmax(T& a, const U& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <typename T, typename U>
T chmin(T& a, const U& b) {
    if (a <= b) return false;
    a = b;
    return true;
}

void yes_no(bool f, string yes = "Yes", string no = "No") { cout << (f ? yes : no) << "\n"; }

unsigned int randxor() {
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void solve() {
    ll seed, n, k, b;
    cin >> seed >> n >> k >> b;
    using P = pair<int, int>;
    vector<P> ps;
    for (int i = 2; i <= b; ++i) {
        if (b % i == 0) {
            int cnt = 0;
            while (b % i == 0) {
                b /= i;
                ++cnt;
            }
            ps.emplace_back(i, cnt);
        }
    }
    vector<vl> cnt(ps.size());
    ll x = seed;
    rep(i, n + 1) {
        ll tmp = x;
        rep(j, ps.size()) {
            ll y = 0;
            while (tmp > 0 && tmp % ps[j].first == 0) {
                ++y;
                tmp /= ps[j].first;
            }
            cnt[j].emplace_back(y);
        }
        x = 1 + (x * x + x * 12345) % 100000009;
    }
    ll ans = 1e18;
    rep(i, cnt.size()) {
        sort(all(cnt[i]));
        ll y = 0;
        rep(j, k) y += cnt[i][j];
        chmin(ans, y / ps[i].second);
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    rep(ti, t) solve();
    return 0;
}