#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main(){ int Q; scanf("%d",&Q); int primes[]={2,3,5,7,11,13,17,19,23,29}; int n_prime=10; for( int qi = 0 ; qi < Q; qi++ ){ int seed,N,K,B; scanf("%d%d%d%d",&seed,&N,&K,&B); int ps[3]; int pcnt[3]; int psize=0; for( int pi = 0 ; pi < n_prime; pi++ ){ int p = primes[pi]; int cnt =0; while(B%p==0){ cnt++; B/=p; } if(cnt>0){ //cout << p << ", "<< cnt; ps[psize]=p; pcnt[psize]=cnt; psize++; } } priority_queue pq[psize]; for( int i = 0 ; i < N+1; i++ ){ long long x = seed; //cout << seed; for( int j = 0 ; j < psize; j++ ){ int p = ps[j]; int cnt = 0; while( seed%p == 0 ){ cnt++; seed/=p; } //cout <<" "< cnt ){ pq[j].pop(); pq[j].push(cnt); } } //cout << endl; long long s= x*x; s%=100000009; s += x*12345; s%=100000009; seed=s+1; } int ans = 500; for( int pi = 0 ; pi < psize; pi++ ){ int div = pcnt[pi]; int sum = 0; for( int j = 0 ; j < K ; j++ ){ sum += pq[pi].top(); pq[pi].pop(); } //cout << sum << "/ "<< div<