Geralt is looking for a new job. He trades his services for coins. For him, it is not only the pleasure of killing monsters or helping old woman find her missing pan, but also the opportunity to haggle with the dirt poor villagers over how much it will cost to save them from unspeakable horrors. The bargaining between Geralt and villagers always follows the same scheme:

Villager: Need Help, will pay 150.
Geralt: For 1000 coins, I can kill any monster for you, even the Griffin.
Villager: Are you crazy? I haven't got that much on me! Ok, let it be 200.
Geralt: It's a difficult job 900 would be fair amount.
Villager: Well, I'll give 250.
Geralt: 800 Hmmm.

Such a dialogue goes on until they agree on a price.

Initial price asked by Geralt for his service is G, Villager's offer V. Villager always increases his amount by the same number I, and Geralt decreases it in the same way by D. Geralt would not ask a sum that is less than that offered by villager. In this case, Geralt will agree with villager's offer. Villagers will act similarly.

You, a Bard, friend of Geralt has to help him find the right price for which both Geralt and Villager's agree.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains four integers V, I, G and D

Output

For each test case, print a single line containing one integer, the amount of money that Villager will have to pay for service of Geralt.

Constraints

$1 \leq \textbf{T} \leq10^{6}$

$1 \leq \textbf{V},\textbf{I},\textbf{G},\textbf{D} \leq10^{6}$

Note: Java programmers should use fast I/O methods.