테트레이션의 나머지

각 테스트 케이스는 $T$개의 경우로 구성된다.

$A, B, M$가 주어진다. ${A \uparrow \uparrow B} (\bmod M)$를 출력한다.

$0^0 = 1$임에 유의한다(적어도 이 문제에서는 그렇다).

제약 조건

• $1 \leq T \leq 1000$
• $0 \leq A, B \leq 10^9$
• $1 \leq M \leq 10^9$

$T$
$A_0$ $B_0$ $M_0$
$A_1$ $B_1$ $M_1$
:
$A_{T-1}$ $B_{T-1}$ $M_{T-1}$

각 줄에 ${A \uparrow \uparrow B} (\bmod M)$를 출력한다.