Migrated from Lutece 1177 pow(a, C(n,m) ) % k

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

One day, Peter was given an easy math problem.

Given four integers $a$, $n$, $m$, $k$ and two formulas $x=a^b( mod\ k)$, $b=C_n^m$, you are supposed to calculate the result of $x$.

However, Peter found that the ranges of $a$, $n$, $m$, $k$ are so large that Peter could not solve it. Could you help him?

Input

The first line contains an integer $T(1 \leq T \leq 500)$ representing the number of test cases.

Each of the following $T$ lines contains four integers $a$, $n$, $m$, $k$. The ranges of them are following.

$1 \leq a \leq 10^{18}$, $0 \leq n \leq 10^{18}$, $0 \leq m \leq 10^{18}$, $1 \leq k \leq 10^5$

Output

Output T lines as the sample output. Output each line as "Case #k: ans". $k$ means the number of test case, $ans$ means the result of those two formulas when given those four integers.

Samples

4
5 0 0 4
100 10 5 3
233035515918638532 700708637 28 32886
999999999992226432 251468460246892460 313092 280

Case #1: 1
Case #2: 1
Case #3: 26244
Case #4: 64

Resources

peterpan