3456. Huge Numbers (Large)

输入格式

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.

2
2 1 2
3 3 2

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.