import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; immutable long MOD = 100000009; long[] primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; void solve() { auto s = readln.split.map!(to!long); auto seed = s[0]; auto N = s[1].to!int; auto K = s[2].to!int; auto B = s[3]; auto A = new long[](N+1); A[0] = seed; foreach (i; 0..N) { A[i+1] = 1 + ((A[i] * A[i] % MOD + A[i] * 12345 % MOD)) % MOD; } long bp; foreach (p; primes) if (B % p == 0) bp = p; auto cnt = new long[](N+1); fill(cnt, 0); foreach (i; 0..N+1) while (A[i] % bp == 0) cnt[i]++, A[i]/=bp; cnt.sort(); long d = 0; while (B % bp == 0) d++, B/=bp; writeln( cnt[0..K].sum / d ); } void main() { auto Q = readln.chomp.to!int; while (Q--) solve; }