SP19722 MTETRA - Modular Tetration

The ordinary arithmetical operations of addition, multiplication and exponentiation are naturally extended into a sequence of [hyperoperations](http://en.wikipedia.org/wiki/Knuth's_up-arrow_notation) as follows. ``` 3×7 = 3 + 3 + 3 + 3 + 3 + 3 + 3 ; there are 7 copies of "3" 3^7 = 3 × 3 × 3 × 3 × 3 × 3 × 3 ; there are 7 copies of "3" 3^^7 = (3^(3^(3^(3^(3^(3^3)))))) ; there are 7 copies of "3" ``` To extend the sequence of operations beyond exponentiation, Knuth defined a “double arrow” operator to denote iterated exponentiation [(tetration)](http://en.wikipedia.org/wiki/Tetration) ^^ in ASCII notation. This gives us some very big numbers, your task will be to compute modular tetration. **_X_^0=1** for all **_X_**, as an empty product. **_X_^^0=1** for all **_X_**, for similar reason.

The first line of input contains an integer **_T_**, the number of test cases. On each of the next **_T_** lines, your are given three integers **_X_**, **_N_**, and **_M_**.

For each test case, you have to print **_X^^N modulo M_**.