Breaking the Diffie-Hellman Key

In this problem, you are given a scenario based on the Diffie–Hellman key exchange protocol. Recall that in the protocol:

1. A fixed prime (P) and its primitive root modulo (P), (g), are publicly agreed upon.
2. Alice chooses a secret random number (a) and sends out (A = g^a \bmod P).
3. Bob chooses a secret random number (b) and sends out (B = g^b \bmod P).
4. Alice computes the shared secret (K = B^a \bmod P) and Bob computes (K = A^b \bmod P).

The secret (K) is (g^{ab} \bmod P), which remains secure as long as the exponents (a) and (b) are large. However, if Alice and Bob choose small numbers (for instance, less than (2^{31})), then the protocol becomes vulnerable.

In this problem, you are given (T) test cases. In each test case, you are provided four integers (P), (g), (A) and (B) where (A = g^a \bmod P) and (B = g^b \bmod P). Your task is to recover the shared secret key (K). You can do so by computing the discrete logarithm to find the secret exponent (a) (or (b)) and then computing (K = B^a \bmod P) (or equivalently (K = A^b \bmod P)).

Note: All given values are less than (2^{31}), so using the baby-step giant-step algorithm for computing the discrete logarithm is sufficient to solve the problem efficiently.

inputFormat

The first line of input contains an integer (T) indicating the number of test cases. For each test case, there is one line containing four space-separated integers: (P), (g), (A) and (B). (P) is a prime number, (g) is a primitive root modulo (P), and (A) and (B) are computed as described above.

outputFormat

For each test case, output a single line containing the shared secret key (K) (computed as (B^a \bmod P), where (a) is the discrete logarithm of (A) to the base (g) modulo (P)).

sample

23 5 8 19

2