import sys
input = sys.stdin.readline
from operator import itemgetter

LIST=[[], [], [2], [3], [2], [5], [2, 3], [7], [2], [3], [2, 5], [11], [2, 3], [13], [2, 7], [3, 5], [2], [17], [2, 3], [19], [2, 5], [3, 7], [2, 11], [23], [2, 3], [5], [2, 13], [3], [2, 7], [29], [2, 3, 5], [31], [2], [3, 11], [2, 17], [5, 7], [2, 3], [37], [2, 19], [3, 13]]
VALUE=[[], [], [1], [1], [2], [1], [1, 1], [1], [3], [2], [1, 1], [1], [2, 1], [1], [1, 1], [1, 1], [4], [1], [1, 2], [1], [2, 1], [1, 1], [1, 1], [1], [3, 1], [2], [1, 1], [3], [2, 1], [1], [1, 1, 1], [1], [5], [1, 1], [1, 1], [1, 1], [2, 2], [1], [1, 1], [1, 1]]

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())

    NOW=seed
    X=[seed]

    for i in range(N):
        NOW=1+(NOW*NOW+NOW*12345)%100000009
        X.append(NOW)

    ANS=1<<30

    for i in range(len(LIST[B])):
        f=LIST[B][i]
        X.sort(key=lambda x:calc(x,f))

        AX=0
        for j in range(K):
            AX+=calc(X[j],f)
        ANS=min(ANS,AX//VALUE[B][i])
            
    print(ANS)