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 java.util.Scanner;

public class E {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        long a = in.nextInt();
        long b = in.nextInt();
        long p = in.nextInt();
        long x = in.nextLong();

        long answer = 0;
        for (long i = 1; i < p; i++) {
            long tmp = (b * modPow(modPow(a, i, p), p - 2, p)) % p;
            long first = ((i - tmp + p) % p) * (p-1) + i;
            if (first <= x)
                answer += (x - first) / (p*(p-1)) + 1;
        }

        System.out.println(answer);
    }

    private static long modPow(long a, long b, long mod) {
        long modPow = 1;
        for (; b > 0; b >>= 1) {
            if ((b & 1) != 0)
                modPow = (modPow * a) % mod;
            a = (a * a) % mod;
        }
        return modPow;
    }

}
