Problem Description

You have $n$ cents at the beginning, and there is a bank that accepts time deposits of your cents.

The time is measured in years and the interest rate is $1/d$ all the time. That is, if you make a time deposit of $c$ cents for $t$ years (both $c$ and $t$ must be integers), then after $t$ years, you can get back $c + \lfloor ct/d \rfloor$ cents from the bank, where $\lfloor x \rfloor$ is the largest integer that is less or equal to $x$. If you make multiple deposits, the interest of each deposit will be calculated independently.

You want to find the best strategy to deposit your cents such that the amount of cents you will own is maximized after $y$ years.

Input Format

The first line is the number of test cases up to 120. For each test case, there are three integers $n$, $d$ and $y$ ($0 < n < 10^8$, $0 < d < 7$, $0 < y < 100$, $n(1+1/d)^y < 2^{64}$).

Output Format

For each test case, output the maximum number of cents you will own after $y$ years.

3
3 2 4
5 6 5
1 1 63

14
10
9223372036854775808