MPOWER - Power it!

For a given numbers x, y and n calculate

xy mod n,

i.e. a number r such that 0 <= r < n and n | (xy - r).

Input


t [the number of test cases <= 10]
x y n [2 <= x, n <= 230, 0 <= y <= 230 - easy (1010000 - hard)

First two test cases are easy, the following four test cases are hard. Threshold is 2 pts (the problem is accepted).

Output

r [such that xy = r (mod n)]

Example 1 (easy)

Input:
2
54015779 489100829 472960975
827371214 966345673 443599139

Output:
350431544
391669493

Example 2 (hard)

Input:
1
29809803 47901912849872523461864631327232122 1008098565

Output:
718185534


Dodane przez:mima
Data dodania:2006-02-27
Limit czasu wykonania programu:1s-8.932s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.