# 素因数分解 import math from operator import itemgetter import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline def fac(x): L=int(math.sqrt(x)) FACT=dict() for i in range(2,L+2): while x%i==0: FACT[i]=FACT.get(i,0)+1 x=x//i if x!=1: FACT[x]=FACT.get(x,0)+1 return FACT FAC=[dict() for i in range(40)] for x in range(2,40): FAC[x]=fac(x) def calc(NOW,x): A=0 while NOW%x==0: NOW//=x A+=1 return A Q=int(input()) for tests in range(Q): seed,N,K,B=map(int,input().split()) LIST=list(FAC[B]) LEN=len(LIST) NOW=seed X=[[0]*LEN for i in range(N+1)] for i in range(LEN): X[0][i]=calc(NOW,LIST[i]) for i in range(N): NOW=1+(NOW*NOW+NOW*12345)%100000009 for j in range(LEN): X[i+1][j]=calc(NOW,LIST[j]) ANS=1<<30 for i in range(LEN): X.sort(key=itemgetter(i)) Y=0 for j in range(K): Y+=X[j][i] ANS=min(ANS,Y//FAC[B][LIST[i]]) print(ANS)