题目描述

一个金矿总共有g克黄金。总共有t秒的时间挖金矿。一开始你手头上没有黄金，你每一秒可以挖1克黄金。你也可以雇佣工人帮你挖金，每个工人每1秒可以挖1克黄金。你必须一次性支付c克黄金给1个工人，该工人才会帮你挖金。工人所挖到的黄金最后全部归属你。工人有无限多。假如你用最优的方法挖金，你最终可以赚到多少克黄金（不超过金矿总储量g）？

输入格式

第一行输入一个整数k，表示测试数据组数，满足1≤k≤5。 接下来k行，每行输入三个整数g、t、c，分别表示金矿总储量、挖金时间、雇佣单个工人的黄金成本。

数据范围

1≤g≤1e18 1≤t≤1e6 1≤c≤1e18

输出格式

共k行，每行输出一个整数，表示每组测试数据的最大可得黄金量。

样例输入1

1
47 10 4

样例输出1

12

样例输入2

5
470000 1000000 50
470000 100000 1234567890123456
470000 100000 57000
470000 100000 42000
567890 4 1

样例输出2

470000
100000
100000
116000
8