There are $$$n$$$ rounds. For each round, you are given three numbers: $$$a$$$, $$$b$$$, and modulus $$$m$$$.
You need to find $$$a^b \bmod m$$$.
If both $$$a = 0$$$ and $$$b = 0$$$, take $$$a^b$$$ as $$$1$$$.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of rounds.
Each of the next $$$n$$$ lines contains three integers $$$a$$$, $$$b$$$, $$$m$$$ ($$$1 \leq a, b \leq 10^9$$$, $$$1 \leq m \leq 10^9 + 7$$$).
For each round, print $$$a^b \bmod m$$$ on its own line.
Input:
3 1000 1 997 2 3 1 2 3 100
Output:
3 0 8
Input:
1 17 7 13
Output:
4