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

Mikasa Ackerman ii da lui Eren urmatoarea functie f(a,b) = a ^ f(a, b - 1) pentru orice b > 1. Stiind ca f(a,1) = a, ajutati-l pe Eren sa calculeze f(a,b) modulo p pentru trei numere a, b si p date.

Mikasa Ackerman ii da lui Eren urmatoarea functie $f(a,b) = a^f(a, b - 1)^$ pentru orice $b > 1$. Stiind ca $f(a,1) = a$, ajutati-l pe Eren sa calculeze $f(a,b) modulo p$ pentru trei numere $a$, $b$ si $p$ date.

h2. Date de intrare

Fişierul de intrare $ackermann.in$ va contine pe prima linie un numar natural T, reprezentand numarul de teste. Pe urmatoarele T linii vor fi cate 3 numere naturale a,b si p.

Fişierul de intrare $ackermann.in$ va contine pe prima linie un numar natural $T$, reprezentand numarul de teste. Pe urmatoarele $T$ linii vor fi cate $3$ numere naturale $a$, $b$ si $p$.

h2. Date de ieşire

În fişierul de ieşire $ackermann.out$ ...

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

h2. Restricţii

* $1 ≤ T ≤ 10$
* $1 ≤ a,b, p ≤ 1.000.000.000$
* $a > p$

* $1 ≤ T ≤ 1.000$
* $1 ≤ a, b, p ≤ 1.000.000.000$

* $a$ este un numar prim

* $a > p$

h2. Exemplu
table(example). |_. ackermann.in |_. ackermann.out |
|3

3 2
2 3
2 4
|27
16

3 2 10
2 3 7
2 4 666013
|7
2

65536
|

Observatii: In exemplu $p > a$. Exemplul este dat asa doar ca sa se inteleaga mai bine. In teste $a > p$.

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