#MMA Contest 015 C

'''
xが与えられるので、x*y mod P≡f となるyの個数を出力せよ。

急に緑diff。
絶対に初心者向けではない。難しすぎる。
'''
gcd=lambda x,y: gcd(y,x%y) if x%y else y
f=lambda:list(map(int,input().split()))

N,M,P,Q=f()
for _ in range(Q):
    x,a=f()
    if a>=P: print(0); continue
    Z=gcd(x,P)
    if a%Z: print(0); continue
    nX=x//Z; nP=P//Z; nA=a//Z
    revX=pow(nX,nP-2,nP)
    basic=revX*nA%nP
    ans=(M-basic)//nP-1
    while (ans+1)*nP<=M-basic: ans+=1
    if a==0: print(ans)
    else: print(ans+1)