DCEPC200  The Prime Minister
DCE Coders mentors got fed up by making problems, they are deciding upon the toughest problem for contest. Everybody started to tease Ankur sir that he can’t make a single tough problem for juniors. He got very angry, now you only handle Ankur sir’s anger (Beware: All the tough number theory problems given to you as assignments are like 2+2=4 for Ankur sir). Here is the problem given by him (Say thanks to Jyoti ma’am that she softens the problem slightly.. ;)). You are given an integer n. There will be 2 different numbers K1 and K2, such that K1*K2 = n.
Both of which satisfies the equation (Totient(K!) mod K) !=0.
You are also given value of a function, F(n) = Sum of squares of factor of n. (example F(20) = 546)
Now you have to calculate the value of x and y which satisfies the equation K1x + K2y = m. Where m is given. Since there are many roots you have to find a single pair (x,y) which satisfies the equation having minimum absolute value of (x +y). If no pair is possible output 1. Else output (abs(x+y)^m)%mod
Input
First line contains T(1<=T<=10000) number of test cases. Each test case consist of single line containing 3 integers n, F(n) and m.
Output
Output T lines , each line contains a single integer ((x+y)^m)%mod.
Constraints
T<=10000
N<=10^8
F(n)<=10^18
M<=100
mod=10000000000283
Example
Input: 1
6 50 3 Output: 0
hide comments
Naivedya Bansal:
20151024 11:57:53
Correct logic..but numerous bugs in implementation, caused me many WAs. :/ 

Ashish Lavania:
20130502 09:40:23
@dce coders: what's the use of the middle input?


Mitch Schwartz:
20121008 17:04:29
Important note: The expected output is actually (abs(x+y)^m)%mod. It was in the previous comments but somehow got deleted.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121008 17:04:29
@dce coders: Thanks :D 

dce coders:
20121008 17:04:29
Solutions have been rejudged due to faulty test data. Some AC solutions got WA now and vice versa. Sorry for the mess :) 

Mitch Schwartz:
20121008 17:04:29
@xilinx: x and y are integers. 

[Rampage] Blue.Mary:
20121008 17:04:29
Are x and y integers, or real numbers? 
Added by:  dce coders 
Date:  20120227 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C C++ 4.3.2 CPP JAVA 
Resource:  Own Problem 