#include<stdio.h>
#include<stdlib.h>

#define M 1000

typedef long long int ln;

int comp(const void *c1,const void *c2){
	int t1=*(int *)c1;
	int t2=*(int *)c2;
	return t1-t2;
}

int main(void){

	int Q;
	scanf("%d",&Q);

	int seed[M];
	int N[M];
	int K[M];
	int B[M];
	int i;
	for(i=0;i<Q;i++){
		scanf("%d%d%d%d",&seed[i],&N[i],&K[i],&B[i]);
	}

	ln X[10001];

	for(i=0;i<Q;i++){
		X[0]=seed[i];
		int j;
		for(j=1;j<=N[i];j++){
			X[j]=1+(X[j-1]*X[j-1]+X[j-1]*12345)%100000009;
		}
		int count[10001];
		for(j=0;j<=N[i];j++){
			count[j]=0;
			while(X[j]%B[i]==0){
				count[j]++;
				X[j]/=B[i];
			}
		}
		qsort(count,N[i]+1,sizeof(int),comp);
		int res=0;
		for(j=0;j<K[i];j++){
			res+=count[j];
		}
		printf("%d\n",res);
	}
	return 0;
}