Little Gilly has been struggling in Maths recently. He's supposed to be learning about exponentiation. His teacher, Viv_CCGS has asked him

"Please multiply ~a~ by itself ~b~ times"

But something is very wrong with Gilly's hearing, and he heard:

"Please raise ~a~ to the power of itself ~b~ times"

Unbeknownst to him, he has just discovered tetration, a fast-growing operation defined as repeated exponentiation.

For integers ~a~ and ~b~, the answer Gilly gets is "the tetration of a to b":

~^{b}a = a \uparrow\uparrow b = \underbrace{a^{a^{a^{\cdot^{\cdot^{a}}}}}}_{b \text{ copies of } a}~

The above notation is known as Knuth's up-arrow notation.

Gilly has been set ~T~ questions, and has written down answers to all of the questions.

You may assume, surprisingly, that Gilly answered all the questions correctly according to his interpretation of the question, meaning he has accurately calculated ~^{b}a~.

However, Gilly's handwriting is illegible, and Viv_CCGS would like to know what numbers he has written down. Since this number may be huge, output the answer ~\mathrm{mod}~ ~M~. The answer will fit in a ~\mathrm{64}~-bit signed integer.

Input Specification

The first line of input contains a single integer, ~T~, the number of questions Gilly has answered. (~1 \le T \le 10000~)

The next ~T~ lines each consist of three space-separated integers ~a_i~, ~b_i~, and ~M_i~, for ~i = 1 \dots T~.

Output Specification

Output ~T~ lines. The ~t~-th line should contain a single integer, Gilly's calculation of ~a_t \uparrow\uparrow b_t \bmod M_t~.

Constraints

• ~1 \le a \le 10^{18}~
• ~1 \le b \le 10^{18}~
• ~1 \le m \le 10^{10}~

Subtask 1

~gcd(a, m) ≠ 1~

Subtask 2

No other constraints.

Sample Input 1

2
3 2 100
2 4 1000

Sample Output 1

27
536

Explanation

~3 \uparrow\uparrow 2 = 3^3 = 27~

~2 \uparrow\uparrow 4 = 2^{2^{2^2}} = 2^{16} = 65536~

~65536 \bmod 1000 = 536~

Notes

Tetration is a right-associative operation, meaning the repeated exponentiation is evaluated from top to bottom, e.g.

• ~2 \uparrow\uparrow 1 = 2~
• ~2 \uparrow\uparrow 2 = 2^2 = 4~
• ~2 \uparrow\uparrow 3 = 2^{2^2} = 16~
• ~2 \uparrow\uparrow 4 = 2^{{2^2}^2} = 2^{16} = 65536~