SPOJ Problem Set (main) 11600. Another Mathematical Problem Problem code: SUMOFPOW

Little Johny suddenly found a great amusement towards numbers. Blame his crush over his maths teacher or anything, it didnt really bother him. One day his teacher gave him a task for finding the solution for ( (P^N) + (Q^N) ) {P power N + Q power N} given P, Q and N. Given Johny's intense crush he solved it very quickly. Seeing this his teacher asked him to calculate ( (P^N) + (Q^N) ) but this time she gave P+Q and P*Q instead of P and Q. Johny set to work and then he understood the difficulty of this problem. Guess what? . It is the same story he asks you for help.


Input :
first line will contain an integer T (<=15) denoting the number of test cases
three integers p+q, p*q and n will be given for each test case in a seperate line
for every test case output the corresponding
output (p^n)+(q^n) in a seperate line

limits : 0<= N <=15, P+Q and P*Q will be in the (-15,15) inclusively.
Note : P, Q, N would be chosen in such a way that the answer fits in a 64 bit signed integer

example:

Input :

5

6 9 11

6 7 10

1 2 3

-5 6 10

2 -4 9

Output:

354294
2808982
-5
60073
38912

---

Added by:	Ranjith Mudalaiyar
Date:	2012-05-26
Time limit:	1s
Source limit:	50000B
Memory limit:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Languages:	All