Help Optimus!

In an alternate reality, due to a prolonged battle between Autobots and Decepticons, planet Cybertron is about to fall. Thanks to the great Bumblebee, a portal has been created between Earth and Cybertron through which Optimus Prime (the leader of the autobots) intends to transfer all surviving autobots to Earth. But there seems to be a problem. Inter-Galactic travel between planets is not cheap. For each group to pass through the portal, a certain amount of energon units are required as fuel which can be purchased from the Galactic Market using Cybertronian currency. Unfortunately, Optimus Prime is running short on Cybertronian money at the moment and so wants to minimize the total cost of travel. He wants to divide the autobots in groups.

After precise calculation by Brain(an autobot scholar), it was found that, the number of energon units required for each group to pass through the portal is

                         (D+F) * X2 + L

where, D is the diameter of the portal in galactic unit, F denotes the electromagnetic field strength, L is total length in galactic unit and X is the number of autobots in the group.

As you can see, traveling between the planets can be quite expensive. However, there is a little bit of relief – due to being mechanical beings, each autobot posses an Eternal Cube by birth.

An Eternal Cube is an object that can be used to generate K energon units. So, the autobots have decided to use up their Eternal Cubes to reduce the amount of energon units that require buying.

Now, Optimus Prime wants to know the maximum number of autobots that he can put in one group such as to minimize the total energon units required for the group to travel. Since, you are a computer programmer and also Prime’s best friend, Optimus reached you for help.

Write a program that will solve the task.

Note: It is guaranteed - the value of D, F, L and K satisfy the fact that the number of autobots (X) is a positive integer and the total energon units required for each group is always a non-negative real number.

Input

The first line of input will contain a single integer T (1 ≤ T ≤ 105) denoting the number of test cases, then T lines of input follow. Each of the next T lines will contain Four space separated integers D, F (1 ≤ D + F ≤ 106), L (1 ≤ L ≤ 1018) and K (1 ≤ K ≤ 2 * 1012).

Output

Print T lines of output. In each line, print a single integer X denoting the maximum number of autobots in each group such as to minimize the total energon units required for the group to travel through the portal.

Sample

Input	Output
2 2 3 10 10 4 1 20 30	1 3