#include #include #include #include #include using namespace std; unsigned long X[100001]; int N, K, B; vector> Bs; vector> factorize(int n) { vector> ret; for(int i = 2; i <= n; i++) { int cnt = 0; while(n % i == 0) { n /= i;cnt++; } if(cnt > 0)ret.emplace_back(i, cnt); } return ret; } void gen_list() { for(int i = 1; i <= N; i++) { X[i] = 1 + ((X[i - 1] + 12345) * X[i - 1]) % 100000009; } } int solve_by_greedy() { vector > Xs(N + 1, vector(3)); for(int i = 0; i <= N; i++) { for(int j = 0; j < 3; j++) { unsigned long tmp2 = X[i]; if(Bs[j].first == 1) { Xs[i][j] = 999999999; }else{ while(tmp2 % Bs[j].first == 0) { tmp2 /= Bs[j].first; Xs[i][j]++; } } } } for(int i = 0; i < 3; i++) { std::sort(Xs.begin(), Xs.end()); vector tmp(3); for(int j = 0; j < K; j++) { for(int k = 0; k < 3; k++) { tmp[k] += Xs[j][k]; } } int t1 = Bs[0].second; int t2 = Bs[1].second; int t3 = Bs[2].second; long ret = tmp[0] / t1; if(ret <= tmp[1] / t2 && ret <= tmp[2] / t3) { return ret; } std::rotate(Bs.begin(), Bs.begin() + 1, Bs.begin() + 3); for(int j = 0; j <= N; j++) { std::rotate(Xs[j].begin(), Xs[j].begin() + 1, Xs[j].begin() + 3); } } return -1; } int main() { int Q; scanf("%d", &Q); while(Q--) { scanf("%ld %d %d %d", &X[0], &N, &K, &B); gen_list(); Bs = factorize(B); int fs = Bs.size(); while(Bs.size() < 3) { Bs.emplace_back(1, 1); } int ret = solve_by_greedy(); if(ret >= 0) { printf("%d\n", ret); } else { int t = 3; int k = 0; if(fs == 3) { printf("%d\n", t / 0); }else if(fs == 2) { printf("%d\n", t / 0); } } } }