DECKEY - Decryption Key
It is a sunny day, and qualifications for level 4 are running in AAST.
The contestants hacked the server and was able to get a file that contain solutions to all problems, but unfortunately the file was encrypted.
They know that the decryption key is in form of (a ^ b) % m (a raised to power b modulo m), and they know a, b and m but they don't know the result of this equation and asked you for help.
Input
First line contains single integer T, then T lines follow, each line contains three integers: a, b, m.
Output
You should print T lines, which is the output of above equation.
Constraints
1 <= T <= 1000
0 <= a <= 1000000000000000000
0 <= b <= 1000000000000000000
1 <= a + b
1 <= m <= 1000000000000000000
Example
Input: 1 2 3 5 Output: 3
Explanation
(2^3)%5 = 8%5 = 3
Added by: | Walid Amin |
Date: | 2016-07-12 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |