#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
map<int,int> prime_factrorize(int n, vector<int> const & primes) {
    map<int,int> result;
    for (int p : primes) {
        if (n < p * p) break;
        while (n % p == 0) {
            result[p] += 1;
            n /= p;
        }
    }
    if (n != 1) result[n] += 1;
    return result;
}
const int inf = 1e9+7;
int main() {
    int q; cin >> q;
    while (q --) {
        int seed, n, k, b; cin >> seed >> n >> k >> b;
        map<int,int> ps = prime_factrorize(b, sieve_of_eratosthenes(b));
        vector<vector<int> > xs;
        for (int i = 0, x = seed; i < n+1; ++ i, x = x *(ll) (x + 12345) % 100000009 + 1) {
            int y = x;
            xs.emplace_back();
            for (auto it : ps) {
                int p = it.first;
                xs.back().push_back(0);
                while (y % p == 0) { ++ xs.back().back(); y /= p; }
            }
        }
        int ans = inf;
        repeat (p,ps.size()) {
            whole(sort, xs, [&](vector<int> const & x, vector<int> const & y) { return make_pair(x[p], x) < make_pair(y[p], y); });
            vector<int> t(ps.size());
            repeat (i,k) repeat (j,ps.size()) t[j] += xs[i][j];
            int j = 0;
            for (auto it : ps) {
                int cnt = it.second;
                setmin(ans, t[j] / cnt);
                ++ j;
            }
        }
        cout << ans << endl;
    }
    return 0;
}