PWRANDMOD - Power and Mod

Exponentiation is a mathematical operation, written as bn, involving two numbers, the base b and the exponent n. When n is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, bn is the product of multiplying n bases:

bn =  b × b × b × ... × b

In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus). Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n. For instance, the expression "5 mod 2" would evaluate to 1 because 5 divided by 2 leaves a quotient of 2 and a remainder of 1, while "9 mod 3" would evaluate to 0 because the division of 9 by 3 has a quotient of 3 and leaves a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3.

Now, you are given the value of a, b and m. print the value of ab mod m.

Input

First line contains the number of test cases t (1 ≤ t ≤ 104). Next t line contains three integers a, b and m. where 1 ≤ a, b ≤ 109 and 1 ≤ m ≤ 264.

Output

For each test case print the answer of the problem.

Sample input

2
2 3 4
3 4 5

Sample output

0
1

Added by:Bhadra
Date:2016-02-18
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU PYTHON PYPY PYTHON3 PY_NBC

hide comments
2020-05-10 08:11:32
is it classical?????

Don't underestimate this question . Costed me 3 WA + 2 TLE :(

Last edit: 2020-05-11 07:23:36
2018-04-27 15:55:49
It is a sb problem!
2018-04-27 15:43:32
why wa?
2017-09-16 19:18:33 [Lakshman]
Please move this to tutorials ASAP.
2017-08-12 20:01:43
Waste of time :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.