Prof.Dr.DP is very famous professor. He is expert (actually legendary grandmaster) in Dynamic Programming. Rinku is greedy girl. She always prefers greedy choices. She has recently learned Dynamic Programming from her programming teacher Prof.Dr.DP. He told her that whenever you have to minimize cost or maximize profit given condition that you have several choices for each time of selection, then dynamic programming can easily be applied there. So, they know that Dynamic programming basically useful for optimization problems. Now Prof.Dr.DP wants to test Rinku’s depth of knowledge in Dynamic Programming. So, He has given her a task. The task was as follows:
Rinku has given an integer number A and she has also given another integer number N. Total number of operations she is allowed to perform are exactly P. In each operation, she has two choices either to add N to her current number or to multiply her current number by N.
What is the maximum number she can make if she do operations in an optimal way?
Input
Input starts with an integer T (1 <= T <= 500000), denoting the number of test cases. Each case contains three space separated integers A, N and P (1 <= A, N <= 10, 1 <= P <=15) as described in the problem statement.
Output
For each case of input, output a single integer number denoting the maximum integer number Rinku can make.
Sample
| Input | Output |
|---|---|
1 5 5 5 | 15625 |
