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 co-existed 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 sceptic.

One day Sunil asked Shankar, "If your argument is right how would you tame a T-REX 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 T-REX would have a maximum capacity C to carry. Let us say the distance is d km. If it is long, the T-REX 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 T-REX 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⁶, d, 1 ≤ d ≤ 10⁵, and C, 1 ≤ I ≤ 10⁶, 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.