你最初拥有 $n$ 美分，有一家银行接受美分定期存款。 时间以年为单位，利率始终为 $1/d$。也就是说，如果你存入 $c$ 美分存期为 $t$ 年（$c$ 和 $t$ 必须均为整数），那么 $t$ 年后，你可以从银行取回 $c + \lfloor ct/d \rfloor$ 美分，其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。如果你进行多次存款，每笔存款的利息将独立计算。 你希望找到最佳的存款策略，使得 $y$ 年后你拥有的美分总数最大化。

输入格式

第一行包含一个整数，表示测试用例的数量，最多为 120 个。 对于每个测试用例，包含三个整数 $n, d$ 和 $y$（$0 < n < 10^8, 0 < d < 7, 0 < y < 100, n(1 + 1/d)^y < 2^{64}$）。

输出格式

对于每个测试用例，输出 $y$ 年后你拥有的最大美分数量。

样例

样例输入 1

3
3 2 4
5 6 5
1 1 63

样例输出 1

14
10
9223372036854775808