== include(page="template/taskheader" task_id="dlog") ==

h4. This problem is sponsored by 'IXIA':http://www.ixiacom.com/

h4. Aceasta problema este sponsorizata de 'IXIA':http://www.ixiacom.com/

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{~5~}$, $3 * 3 = 4 (9 mod 5)$.

Se da un numar natural prim $P$. Definim $Z{~P~}$ ca fiind multimea tuturor resturilor posibile $modulo P$, adica ${0, 1, 2, ... P - 1}$. Toate operatiile asupra numerelor din $Z{~P~}$ se realizeaza $modulo P$. De exemplu, in $Z{~5~}$, $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{~5~}$, because: $2^1^ = 2, 2^2^ = 4, 2^3^ = 3, 2^4^ = 1$ (all operations are made $modulo 5$). For $Z{~7~}$, however, $2$ is not a generator as $5$ cannot be obtained through the operation described.

Spunem despre un numar natural $G$, din multimea ${1, 2, ... P - 1}$ ca este generator al lui $Z{~P~}$ cu inmultirea daca, ridicandu-l la anumite puteri, putem obtine toate numerele din $Z{~P~} \ {0}$. De exemplu, $2$ este generator al lui $Z{~5~}$, deoarece: $2^1^ = 2, 2^2^ = 4, 2^3^ = 3, 2^4^ = 1$ (toate operatiile sunt realizate $modulo 5$). Pe de alta parte, $2$ nu este un generator al lui $Z{~7~}$, deoarece nu se poate obtine numarul $5$ prin operatia descrisa.

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)$.

Dandu-se un numar prim $P$, un numar $G$, generator al lui $Z{~P~}$, si un numar $Y$ apartinand multimii ${1, 2, 3, ... P - 1}$, sa se gaseasca $X$ minim, cu proprietatea ca $G^X^ = Y (mod P)$.

h2. Input

h2. Date de intrare

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.

Fişierul de intrare $dlog.in$ va contine pe prima linie $T$, numarul de query-uri din fisierul de intrare. Pe fiecare dintre urmatoarele $T$ linii se va gasi cate un query, in formatul $P, G, Y$, cu semnificatia de mai sus.

h2. Output

h2. Date de ieşire

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.

Fişierul de ieşire $dlog.out$ va contine raspunsurile la cele $T$ query-uri, pe linii separate.

h2. Restrictions

h2. Restricţii

* $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]$**

* **Pentru fiecare dintre cele $T$ teste, raspunsul trebuie sa se regaseasca in intevalul $[0 .. P - 1]$**

h2. Example

h2. Exemplu

table(example). |_. dlog.in |_. dlog.out |
|3

4
|

h3. Sample test explanation

h3. Explicaţie

$2^0 MOD 3 = 1 MOD 3 = 1$
$3^3 MOD 5 = 27 MOD 5 = 2$

7766