题目描述

你最初拥有 $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$ 年后你能够拥有的最大美分数目。

3
3 2 4
5 6 5
1 1 63

14
10
9223372036854775808

提示

翻译由 DeepSeek V4 Pro 完成