The Diffie-Hellman key exchange protocol is a simple and effective method for key exchange. It allows two parties to establish a secure key $K$ over an insecure channel (which may be eavesdropped upon) for use in subsequent encrypted communication.

Assuming the two parties are named Alice and Bob, the protocol works as follows (where $\text{mod}$ denotes the modulo operation):

1. The protocol specifies a fixed prime $P$ and a primitive root $g$ modulo $P$. The values of $P$ and $g$ are public and do not need to be kept secret.
2. Alice generates a random number $a$ and calculates $A = g^a \pmod P$, then sends $A$ to Bob over an insecure channel.
3. Bob generates a random number $b$ and calculates $B = g^b \pmod P$, then sends $B$ to Alice over an insecure channel.
4. Bob calculates $K = A^b \pmod P$ using the received $A$, and Alice calculates $K = B^a \pmod P$ using the received $B$.
5. Both parties obtain the same key $K$, which is $g^{ab} \pmod P$. $K$ can then be used as a secure key for subsequent communication.

As we can see, the only information intercepted during this process is $A$ and $B$, while $a$, $b$, and $K$ remain secret. Given the four values $A$, $B$, $P$, and $g$, it is not easy to calculate $K$, so $K$ can serve as a secure key.

Of course, security is relative; the security of this protocol depends on the size of the values. Usually, $a$, $b$, and $P$ are chosen to be large integers with hundreds of digits to avoid being cracked. However, if Alice and Bob are lazy and, to simplify implementation, choose values smaller than $2^{31}$, then cracking their key becomes much easier.

Input

The first line of the input contains two space-separated integers $g$ and $P$. The second line contains an integer $n$, representing that Alice and Bob have performed $n$ connections (i.e., the protocol was run $n$ times). The next $n$ lines each contain two space-separated integers $A$ and $B$, representing the values of $A$ and $B$ intercepted during a specific connection.

Output

The output contains $n$ lines, each containing one integer $K$, representing the key cracked for each connection.

Examples

Input 1

3 31
3
27 16
21 3
9 26

Output 1

4
21
25

Constraints

• For 30% of the data: $2 \le A, B, P \le 1000$
• For 100% of the data: $2 \le A, B < P < 2^{31}$, $2 \le g < 20$, $1 \le n \le 20$