Hand of Midas is an item in Dota2 that provides significant gold to the hero who uses it. Upon use, it kills a non-hero target for $$$160$$$ gold. Hand of Midas has a cooldown of $$$a$$$ seconds, meaning it can only be used again after $$$a$$$ seconds of last use.
Refresher Orb is another powerful item in Dota2. When used, it refreshes the cooldowns of all the user's other abilities and items, allowing the user to cast spells and use items again immediately. For example, if your Hand of Midas is in cooldown, while your Refresher Orb is not, you can use Refresher Orb so that you can use Hand of Midas immediately. Refresher Orb has a cooldown of $$$b$$$ seconds. Apparently, using Refresher Orb doesn't refresh the cooldown of Refresher Orb itself.
You have bought both Hand of Midas and Refresher Orb in the game, and now you want to maximize the gold you get in the next $$$m$$$ seconds! Currently, both your Hand of Midas and Refresher Orb are not in cooldown. We assume that the time you use Hand of Midas and Refresher Orb can be neglected.
This problem contains multiple test cases. The first line of input contains an integer $$$T$$$ $$$(1\leq T \leq 10\,000)$$$, denoting the number of test cases.
For each test case, the input contains one line with three integers $$$a,b,m$$$ $$$(1\leq a,b\leq 10^6,0\leq m\leq 10^6)$$$, denoting the cooldown of Hand of Midas, the cooldown of Refresher Orb, and the amount of time you have to maximize your gold, respectively.
It is guaranteed that the sum of $$$a$$$, $$$b$$$, and $$$m$$$ over all test cases does not exceed $$$10^7$$$, respectively.
For each test case, output an integer in a line, denoting the maximum number of gold you can get.
6 50 100 0 40 10 50 10 40 50 1 1 1000000 60 200 960 60 185 905
320 1120 1280 320000320 3520 3360
For the first test case of the sample test, the optimal strategy is to use Hand of Midas, then immediately use Refresher Orb and then Hand of Midas, obtaining a total of $$$160\times 2=320$$$ gold. This strategy is described in the following picture (The ball-like item is Refresher Orb, while the hand-like item is the Hand of Midas).
For the second test case of the sample test, the optimal strategy is described in the following picture, obtaining a total of $$$160\times 7=1\,120$$$ gold.
For the third test case of the sample test, the optimal strategy is described in the following picture, obtaining a total of $$$160\times 8=1\,280$$$ gold.
