A1. Huge Numbers (Small)

**单点时限: **2.0 sec

**内存限制: **256 MB

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.

- Limits: $1 \le T \le 100$.
- Small dataset: $1 \le A \le 10, 1 \le N \le 10, 1 \le P \le 10$.
- Large dataset: $1 \le A \le 10^5, 1 \le N \le 10^5, 1 \le P \le 10^5$.

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.

Input

2 2 1 2 3 3 2

Output

Case #1: 0 Case #2: 1

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!} = 36 = 729$ is divided by 2, which is 1.

通知

比赛状态发生变化，点 OK 刷新。

通知