Bacteria Growth (Small)

Pascal studies microorganisms and found a bacterium with an unusual growth pattern. If $x$ of them are present at one moment, then in an ideal environment there are $x^x$ of them one hour later.

Given three integers $A$, $B$ and $C$, compute how many bacteria there are $B$ hours after a colony of $A$ bacteria starts. Every hour the count $x$ turns into $x^x$, and that change happens $B$ times. The answer grows very large, so print its remainder modulo $C$.

The first line contains the number of test cases $T$. Each of the following $T$ lines contains one test case.

A test case is three integers separated by spaces: $A$, $B$ and $C$, in that order.

Constraints

• $1 \le T \le 500$
• $1 \le A \le 1000$
• $1 \le B \le 1000$
• $1 \le C \le 1000$

For each test case, print one line in the following format.

Case #X: N

$X$ is the number of the test case, counting from 1, and $N$ is the number of bacteria after $B$ hours, taken modulo $C$.