TREX  Taming a TREX
Although evolution theory suggests that mammals started to dominate this world only after the mass extinction of the dinosaurs, there are some people who say man and dinosaurs may have coexisted for some time. Some argue that man even tamed and used some of these animals like the Flintstones. Shankar is such a believer and Sunil is a skeptic.
One day Sunil asked Shankar, "If your argument is right how would you tame a TREX and what would you use it for?". Shankar replied, "We can use it for cow transportation from one village to another and we can keep it calm by feeding it at constant intervals". Sunil argued that the TREX would have a maximum capacity C to carry. Let us say the distance is d km. If it is long, the TREX would eat all the cows before it reaches the other village. Shankar argued that he knew a method that takes the maximum possible number of cows M to the destination. Sunil replied, "Oh really? I will give a few conditions. The TREX will eat 1 cow every km until it reaches the destination. It may do so at any time during a 1 km stretch. So,there can not be a situation where the TREX has no cow to eat. If you drop cows in the middle, you can do so only at distances which are a multiple of 1 km. And, finally all the cows at the destination need to be alive i.e you can not cut a cow (fractions are not allowed)".
Shankar was stunned. He needs your help. Given I (the number of cows at the starting village) , d and C find M, the maximum number of cows that can be taken to the destination subject to the mentioned constraints.
Input
There will be multiple test cases in the input. The input begins with a line containing a single integer n,n ≤ 300, which gives the number of test cases. Then n lines follow each containing the three integers I, 1 ≤ I ≤ 10^{6}, d, 1 ≤ d ≤ 10^{5}, and C, 1 ≤ I ≤ 10^{6}, in that order separated by spaces. d is in kilometers.
Output
For each test case print on a separate line the maximum number of cows that can be transported to the destination village under the given conditions.
Example
Input: 2 3000 1000 1000 30 10 10 Output: 533 5
Note:
A few test cases have been added and this problem has been rejudged on January 25th, 2009.
hide comments
Bhavik:
20140404 16:56:13
very nice question...if you can find how 2nd test case is solved you solve the question itself:))


SanchitK:
20131216 08:10:39
@swarnaprakash didnt understand the problem.


Nilendu Das:
20121211 11:17:22
Dropping means leaving behind..


.::Manish Kumar::.:
20110501 00:09:24
Problem statement is not clear.

Added by:  Swarnaprakash 
Date:  20090117 
Time limit:  0.349s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Kurukshetra 09 OPC 