Fişierul intrare/ieşire:	dlog.in, dlog.out	Sursă	Infoarena Cup 2012
Autor	Cosmin Gheorghe	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.25 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Dlog

This problem is sponsored by IXIA

A prime integer P is given. We define Z_P as the set of all possible remainders modulo P, that is {0, 1, 2, ... P - 1}. Any operation on the numbers of Z_P is done modulo P. For example, in Z₅, 3 * 3 = 4 (9 mod 5).

We call a natural number G, belonging to the set {1, 2, ... P - 1}, a generator of Z_P with regard to multiplying if by raising it to some powers we can obtain any number in Z_P \ {0}. For example 2 is a generator of Z₅, because: 2¹ = 2, 2² = 4, 2³ = 3, 2⁴ = 1 (all operations are made modulo 5). For Z₇, however, 2 is not a generator as 5 cannot be obtained through the operation described.

Given a prime number P, a generator G of Z_P and a number Y belonging to the set {1, 2, 3, ... P - 1} you must find the minimum X with the property that G^X = Y (mod P).

Input

The input file dlog.in contains on its first line a natural number T representing the number of queries in the input file. Each of the next T lines contains one query in the format P, G, Y according to the description above.

Output

The output file dlog.out must contain T lines. The i-th line will contain the answer to the i-th query in the input file.

Restrictions

• 1 ≤ T ≤ 1.000
• 2 ≤ P ≤ 2.000.000
• 1 ≤ G, Y < P
• The result printed for each test should be in the interval [0 .. P - 1]

Example

Sample test explanation

2^0 MOD 3 = 1 MOD 3 = 1
3^3 MOD 5 = 27 MOD 5 = 2
3^4 MOD 7 = 81 MOD 7 = 4

Cum se trimit solutii?