Fib&&Gib

Time Limit: 1000ms

Memory Limit: 32768Kb

Description

Have you heard the famous sequence called the Fibonacci Sequence, or Fib for short? HJWAJ loves this sequence very much. One day HJWAJ, getting bored, started playing with it again.

But HJWAJ’s girlfriend, wdyswdjl, hates maths very much. She doesn’t want HJWAJ to be immersed in his maths world. She said, “HJWAJ, why do you love sequences so much? If I make a sequence based on Fib, you will never like playing with it again. Let’s bet!” So she created another sequence called Gib Sequence. If HJWAJ couldn’t work out with the sequence, he would get frustrated and his GF would never permit him to play with maths again. Now HJWAJ have no idea to deal with the sequence, so it’s time for you, the most brilliant programmer, to help him.

The Gib Sequence is defined by four variables a, b, n, p. For any group of given (a, b, n, p), the sequence is denoted as

Input

The first line contains an integer T(T<=20), representing T cases followed.

Then comes T lines. Each line contains 4 integers, a, b, n, p.All the integers are positive and will never be larger than 2000000000(i.e.2*10^9), p is an odd prime number and a, b < p.

Output

For each testcase, first output “Case #i: ”, then a number followed representing the result of the sequence. The variable i means the ith testcase.

Sample Input

2
2 3 1 10007
2 3 2 10007


Sample Output

Case #1: 40
Case #2: 392


Hint

(1)

The Fib Sequence is denoted as below:

Fib(n)=1, n==0 || n==1;

Fib(n)=Fib(n-1) + Fib(n-2), n>1.

(2)

In this problem you may need to use a famous theorem in number theory called Euler’s Theorem.

It states that:

Given two positive integers a and n, if a and n are coprime, then aphi(n)mod n=1

We define phi(n) as the number of integers which are not greater than n and are coprime with n.

(3)

In this problem you may need to use a commonly used skill in ACM. If you have a linear recursion formula to calculate, you may use the matrix to prior the calculation—I think all of you have learnt linear algebra, right? Here is an example below.

Given A0=a, A1=b, An = p*A(n-1) + q*A(n-2)(n>2). You can make such matrix:

So, after iterating we can get:

Then, assuming A is a matrix, to calculate A^n, we can use binary algorithm below:

If n is odd, A^n = ( A^(n/2) )^2 *A;

If n is even, A^n = ( A^(n/2) )^2.

This can save large amount of time so you may avoid from TLE.