Secret Code

Question

When you want to send a message, could you imagine what would happen if you don't encrypt it? The Hackers may get your information, which may be critical for you such as your bank account and password. So we try to encrypt the message into "Secret Code" before sending it. But now your task is not to encrypt the message, but to "operate" on the "Secret Code".

First of all, I will tell you how we encrypt a single small letter C into the "Secret Code" (Note that we only take small letters into consideration).

1. We could get a value A from C by the following expression.

A = Fun(C); //Here Fun(C) generates an integer in the range[1, 2^31 - 1] associated with C, but we don't care what the function's expression is;

1. Let B = Fun2(theASCIIvalueOf(C)), note theASCIIvalueOf('a') is 97 and Fun2(theASCIIvalueOf(C)) generates an integer in the range[1, 2^31 - 1] associated with theASCIIvalueOf(C), but we don't care what the function's expression is;

2. Calculate D = AB mod P, here P is a given integer.

3. D is the "Secret Code" for the small letter C.

Now I will tell you how to "operate" the "Secret Code": Find all the numbers that satisfy the following rules:

1. Ax = D (mod P)

2. 0 <= x <= M, here M is a given integer.

Now your task is so simple: you are given A, P, D and M, please tell me the number of numbers that satisfy the two rules above.

Input

There are multiply cases (<30), process to the end of file.

Every case contains only four integers indicating A, P, D, M (1 <= A, P < 2^31, 0 <= D < P, 1 <= M < 2^63).

Ouput

For each case, you should output a single line indicates the answer as describe above.

Sample Input

2 16 8 10
5 10 5 11
Sample Output

1
11

Answer 1

http://blog.csdn.net/codebattle/article/details/43086679