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