P16634 [GKS 2017 #G] Huge Numbers

Professor Shekhu has another problem for Akki today. He has given him three positive integers $A$, $N$ and $P$ and wants him to calculate the remainder when $A^{N!}$ is divided by $P$. As usual, $N!$ denotes the product of the first $N$ positive integers.

The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each line contains three integers $A$, $N$ and $P$, as described above.

For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from $1$) and $y$ is the answer.

In Sample Case $1$, the answer is the remainder when $2^{1!} = 2$ is divided by $2$, which is $0$. In Sample Case $2$, the answer is the remainder when $3^{3!} = 3^6 = 729$ is divided by $2$, which is $1$. ### Limits $1 \le T \le 100$. **Small dataset (Test set 1 - Visible)** $1 \le A \le 10$. $1 \le N \le 10$. $1 \le P \le 10$. **Large dataset (Test set 2 - Hidden)** $1 \le A \le 10^5$. $1 \le N \le 10^5$. $1 \le P \le 10^5$.