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

Added by:dce coders
Date:2012-02-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem

hide comments
2015-10-24 11:57:53 Naivedya Bansal
Correct logic..but numerous bugs in implementation, caused me many WAs. :/
2013-05-02 09:40:23 Ashish Lavania
@dce coders: what's the use of the middle input?
EDIT : None..... easy problem, was just using the wrong way to power up

Last edit: 2013-05-03 18:49:00
2012-10-08 17:04:29 Mitch Schwartz
Important note: The expected output is actually (abs(x+y)^m)%mod. It was in the previous comments but somehow got deleted.

Thanks for fixing the data; it's a bit surprising that it went on that long, and with several solvers, before the mistake was spotted.

Reply - Yes i cleaned up all comments and it might have got deleted. And indeed it took so long and i am surprised too that none of the solvers pointed out that mistake and all went ahead with the wrong approach. However it was few days back that one of my friend pointed out that bug :)

Last edit: 2012-10-08 16:30:27
2012-10-08 17:04:29 (Tjandra Satria Gunawan)(曾毅昆)
@dce coders: Thanks :-D
2012-10-08 17:04:29 dce coders
Solutions have been rejudged due to faulty test data. Some AC solutions got WA now and vice versa. Sorry for the mess :)
2012-10-08 17:04:29 Mitch Schwartz
@xilinx: x and y are integers.
2012-10-08 17:04:29 [Rampage] Blue.Mary
Are x and y integers, or real numbers?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.