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

Aceasta problema este sponsorizata de IXIA

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₅, 3 * 3 = 4 (9 mod 5).

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₅, deoarece: 2¹ = 2, 2² = 4, 2³ = 3, 2⁴ = 1 (toate operatiile sunt realizate modulo 5). Pe de alta parte, 2 nu este un generator al lui Z₇, deoarece nu se poate obtine numarul 5 prin operatia descrisa.

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

Date de intrare

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.

Date de ieşire

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

Restricţii

• 1 ≤ T ≤ 1.000
• 2 ≤ P ≤ 2.000.000
• 1 ≤ G, Y < P
• Pentru fiecare dintre cele T teste, raspunsul trebuie sa se regaseasca in intevalul [0 .. P - 1]

Exemplu

Explicaţie

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?