CNTEASY - Counting Is Easy
The famous “Motu king“ –Rabbi has just received Ktaka from lazy boy BG. He wants to spend this money as soon as possible , so that no one will ask him for party. Today he has gone for shopping mall. As he is very fond of mathematics series, he would like to buy things whose prices are of the form a, a + d, a + 2 * d ... a + n * d. (That means, if he buy first thing of price a, then secondly he must buy thing of price a + d, then a + 2 * d, and so on). But, unfortunately, there are only one thing of each price. So, your task is to suggest him maximum how many things he can buy within his money limit.
(Note that: his money may not be finished after buying.)
Input
Input starts with an integer T denoting the number of test cases.
Each case contains three integers a, d, k denoting the price of the first thing he will buy, difference between two consecutive price of things as described above and total money he received respectively.
Constraints:
T <= 200000 (2 * 10^5)
1 <= a <= 100000000 (10^7)
0 <= d <= 5
1 <= k <= 1000000000000 (10^12)
Output
For each case of input, print one line of output denoting the total things he could buy.
Example
Input: 1 1 1 3 Output: 2
hide comments
nadstratosfer:
2018-10-04 21:05:49
Possibly damaged testfile: trying to read T cases leads to crash while reading til EOF gives WA. |
Added by: | Raihat Zaman Neloy |
Date: | 2015-09-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |