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)) 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

The 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 separate line.

Output

For every test case output the corresponding output (p^n) + (q^n) in a separate line.

Constraints

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