FUNMODSEQ  Funny Modular Sequence
Lets define a funny modular sequence as a sequence such that a_{1} x a_{2}=1 (mod p), a_{2} x a_{3}=1 (mod p) ..., a_{n1} x a_{n} = 1 (mod p). Also, a_{1}, a_{ 2}, a_{ 3}, ... a_{n} must be less than p and greater than or equal to 0. Given one element, a_{1}, find the sum of the entire funny modular sequence of length n. If, for any a_{i}, where i>=1, there exists no a_{i+1} such that a_{i}x a_{i+1} = 1 (mod p), output 1.
Note: p is not necessarily prime.
Input:
The first line contains T, the number of test cases.
T lines follow, each containing a_{1}, p, and n.
Output:
For each test case, output one line, the required sum.
Constraints:
1<=T<=10^{5}
1<=a_{1}<=10^{5}
1<=n<=10^{9}
a_{1} < p <=10^{9}
Sample Input:
2
2 3 2
3 7 2
Sample Output:
4
8
Explanation
In the first test case, the funny modular sequence will be 2, 2, which has a sum of 4.
In the second test case, it will be 3, 5, which has a sum of 8.
hide comments
nadstratosfer:
20190320 04:46:33
Testcases are uncompromising, which is a shame as I've had a blast exploring the patterns here and building and optimizing a solution based on my findings, on and off for 2 days, only to find out it has to TLE. Finally had to turn to wikipedia and after 15mins a played out NT trick did the job. And the fun was over. Disappointed. 

:D:
20160913 00:44:40
It must be added that a{i+1} in the condition for 1 can be out of the sequence. 

TKD:
20160627 13:58:17
sequence in increasing order??


Min_25:
20160625 13:10:06
[ Note ]


krunner:
20160625 02:25:38
@Piyush: could you please check submission 17172921 ? Shouldn't time limit be increased for Java programs ? I can see one Python submission in 1.84 sec whereas limit on this page is 1 sec Thank you for looking


geeta:
20160622 22:08:06
should the sequence be in increasing order?? plz give a test case for which output is 1!!


pvsmpraveen:
20160617 17:10:35
Nice Question :) !!


wisfaq:
20160617 13:30:20
If you ask me to calculate something mod p it is very deceptive to use p's that aren't prime.


lt:
20160617 12:09:02
Awesome problem! Ac in one go. :)


akshayvenkat:
20160617 07:26:57
@Piyush i think the sample input given in the problem must be

Added by:  Piyush Kumar 
Date:  20160616 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Hackerearth Monthly Contest 