Given an integer x. Your task is to find out how many positive integers n (1 ≤ n ≤ x) satisfy $$$n ⋅ a^n ≡ b   (mod\;p), where a, b, p$$$ are all known constants.

Input

The only line contains four integers a,b,p,x (2 ≤ p ≤ 10^6+3, 1 ≤ a,b < p, 1 ≤ x ≤ 10^{12}). It is guaranteed that p is a prime.

Output

Print a single integer: the number of possible answers n.

Examples

Input

2 3 5 8


Output

2


Input

4 6 7 13


Output

1


Input

233 233 10007 1


Output

1

Note

In the first sample, we can see that n=2 and n=8 are possible answers.
import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))

def gcd2(a, b):
    l = []
    while b:
        l.append(divmod(a,b))
        a, b = b, a%b
    x, y = 1, 0
    for aa,bb in l[::-1]:
        x, y = y, x - aa*y
    return a, x, y

def modinv(x, M):
    a,xx,yy = gcd2(x,M)
    return a,xx%M

def solve(a,b,n):
    g,xx,yy = gcd2(a,n)
    if b%g!=0:
        return None
    a //= g
    n //= g
    b //= g
    ainv = modinv(a, n)[1]
    x = ainv*b%n
    return x

def crt(rs, ms):
    r0 = 0
    m0 = 1
    for r1,m1 in zip(rs, ms):
        if m0<m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        if m0%m1==0:
            if r0%m1 != r1:
                return None,None
            else:
                continue
#         print(m0,m1)
        g,im = modinv(m0, m1)
        u1 = m1//g
        if (r1-r0)%g!=0:
            return None,None
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0<0:
            r0 += m0
    return r0,m0

a,b,p,x = list(map(int, input().split()))

c = 1
index = [[] for _ in range(p)]
for i in range(p-1):
    index[c].append(i)
    c *= a
    c %= p
ans = 0

for i in range(1,p):
    j = b*pow(i, p-2, p)%p
    for jj in index[j]:
        res = crt((i, jj), (p, p-1))
        if res[0] is not None:
            r,m = res
#             print(res)
            ans += max(0, x-r+m)//m
print(ans)