#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

int isqrt(int n) {
    int x = n;
    int y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + n / x) / 2;
    }
    return x;
}

std::unordered_map<int, int> factorization(int n) {
    std::unordered_map<int, int> res;
    int tmp = n;
    const int sq_n = isqrt(n);
    for (int i = 2; i < sq_n + 1; ++i) {
        if (tmp % i == 0) {
            int cnt = 0;
            while (tmp % i == 0) {
                cnt += 1;
                tmp /= i;
            }
            res.emplace(i, cnt);
        }
    }
    if (tmp != 1) res.emplace(tmp, 1);
    if (res.empty() && n != 1) res.emplace(n, 1);

    return res;
}

int solve(int seed, int N, int K, int B) {
    std::vector<long long> X(N + 1);
    X.at(0) = seed;
    for (int i = 1; i < N + 1; ++i) {
        const auto &x = X.at(i - 1);
        X.at(i) = 1 + (x * x + x * 12345) % 100000009;
    }
    const auto f = factorization(B);
    int res = N;
    for (const auto &[k, v]: f) {
        std::vector<int> factor_count;
        for (const auto &x: X) {
            auto tmp = x;
            int cnt = 0;
            while (tmp % k == 0) {
                cnt++;
                tmp /= k;
            }
            factor_count.push_back(cnt);
        }
        std::sort(factor_count.begin(), factor_count.end());
        int cnt_sum = 0;
        for (int i = 0; i < K; ++i) {
            cnt_sum += factor_count.at(i);
        }
        if (res > (cnt_sum / v)) res = cnt_sum / v;
    }
    return res;
}

int main() {
    int Q;
    std::cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int seed, N, K, B;
        std::cin >> seed >> N >> K >> B;
        std::cout << solve(seed, N, K, B) << std::endl;
    }
}