LOGPOWER - n-th Power

no tags 

Given an integer A, N and M, calculate R = AN modulo M, ie. the remainder after dividing N-th power of A by the modulus M.

Input

First line: positive integer T - numer of test cases, T<1000.
Next T lines contain 3 integers each: Ai, Ni and Mi.
Data constraints:
-230 < Ai < +230
0 < Ni < +260
2 < Mi < +230

Output

For each of test cases, output the number Ri - one in each line.

Example

Input:
6
1 2 3
4 5 6
7 8 9
12 34 56
78 90 123
4567890 123456789012 34567890


Output:
1
4
4
16
42
781950

hide comments
Mitch Schwartz: 2010-09-24 23:14:11

For those wondering, it seems that (-2)^3 mod 100 can be either -8 or 92, both acceptable.


Added by:Robert Rychcicki
Date:2009-01-10
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET