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

Se dau $2$ numere naturale $N$ si $M$. Sa se determine cel mai mare divizor comun dintre $N_secund = (2 ^ N) - 1$ si $M_secund = (2 ^ M) - 1$. Raspunsul trebuie afisat $modulo P$.

Se dau $2$ numere naturale $N$ si $M$. Sa se determine cel mai mare divizor comun dintre $N_secund = 2^N^ - 1$ si $M_secund = 2^M^ - 1$. Raspunsul trebuie afisat $modulo P$.

h2. Date de intrare

Fişierul de intrare $gcd.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$.

Fişierul de intrare $gcd.in$ va contine pe prima linie un numar natural $T$, reprezentand numarul de teste. Pe urmatoarele $T$ linii vor fi cate $3$ numere naturale $N$, $M$ si $P$.

h2. Date de ieşire

Fişierul de ieşire $gcd.out$ va contine un singur numar reprezentand raspunsul $modulo P$.

Fişierul de ieşire $gcd.out$ va contine $T$ linii, pe linia $i$ aflandu-se raspunsul pentru testul $i$.

h2. Restricţii
* $1 ≤ N,M,P ≤ 1.000.000.000$

* $A ^ B reprezinta A ridicat la puterea B$

* $1 ≤ T ≤ 100.000$
 

h2. Exemplu
table(example). |_. gcd.in |_. gcd.out |

|2 3 100

|2
2 3 100
2 4 100

|1

3

|
h3. Explicaţie

Cel mai mare divizor comun dintre $3$ si $7$ este $1$.

Cel mai mare divizor comun dintre $3$ si $7$ este $1$ iar cel mai mare divizor comun dintre $3$ si $15$ este $3$.

== include(page="template/taskfooter" task_id="gcd") ==