LCPCP2 - Johnny Learns Modular exponentiation

no tags 

After Johnny solved problem A in LCPC2012 practice contest he decided to read more about modulo operation so he read the following article.

Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography.

A "modular exponentiation" calculates the remainder when a positive integer b (the base) raised to the e-th power (the exponent), and the total quantity is divided by a positive integer m, called the modulus. In symbols, this is, given base b, exponent e, and modulus m, the modular exponentiation c is: c = (b^e) mod M

For example, given b = 5, e = 3, and m = 13, the solution c is the remainder of dividing 5^3 by 13, which is the remainder of 125 / 13, or 8.

If b, e, and m are non-negative, and b < m, then a unique solution c exists with the property 0 ≤ c < m.

Input

Input will start with T number of test cases. Followed by T test cases each test has three integers 0 < b < 109 and 018 and 0 < m < 109

Output

For each test case, output the result using the following format:

k. x

Where k is the test case number (starting at 1), a single period, a single space, then the answer x.

Sample

Input
1
3 2 8

Output
1. 1

hide comments
abd alkader: 2012-11-22 21:17:38

easy task remove it even from tutorial

:D: 2012-10-06 23:07:30

Agree. Still it's a very good for tutorial, since you need to use fast multiplication, that is one of the basic building blocks in other problems.

Francky: 2012-10-06 18:44:45

+1 with Alex, hide this one too, please.
Why not another hello_world, or add(a, b) ?

Alex Anderson: 2012-10-06 17:59:48

I want to say this should go into tutorial, but there are already multiple problems in both classical and tutorial that are this exact thing (or harder). But it is part of a contest... eh, I dunno. But I don't think it should be worth any points on spoj.


Added by:Gareev
Date:2012-10-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:LCPC 2012