GG NO RE OMG CHEATZ

You do not need to know the board game Risk to solve this problem. Every die in this problem is a six sided die.

Rizk is a Bulgarian variant of Risk. Two players fight, each commanding an army. On your turn you either attack or add units to your army, never both. An attack works like this.

Player A attacks with $U_a$ units and player B defends with $U_b$ units. The attacker has $D_a$ dice available and the defender has $D_d$ dice available. One attack repeats the following steps.

1. Player A rolls $\min(D_a, U_a)$ dice.
2. Player B rolls $\min(D_d, U_b)$ dice. This differs from ordinary Risk.
3. Both players sort their dice from highest to lowest and compare them pair by pair. For example, if player A rolled 2, 5, 1, 3 and player B rolled 4, 1, 3, then 5 meets 4, then 3 meets 3, then 2 meets 1. The leftover low rolls of the player who threw more dice take part in no comparison.
4. In each comparison the losing player loses one unit. The defender wins ties. In the example above, A loses 1 unit and B loses 2 units.
5. If both players still have at least 1 unit, go back to step 1.

The player who still has units at the end wins the battle. Exactly one player always has units left.

Mike and his brother have been playing for hours. Neither dares to attack, because both fear losing. It is Mike's turn, and he has decided to cheat a little in order to win. He attacks only if his chance of winning this turn is at least 75 percent. Mike has $X$ units and his brother has $Y$ units. How many units does Mike have to sneak into the game so that his chance of winning this turn is at least 75 percent?

The first line contains one integer $T$, the number of test cases. Each of the next $T$ lines contains four integers $D_a$, $D_d$, $X$, $Y$ separated by spaces, with the meaning given above.

• $1 \le T \le 30$
• $1 \le D_a, D_d \le 4$
• $1 \le X, Y \le 500$
• No test case has a winning probability closer to $0.75$ than $10^{-6}$ when a unit is added to or removed from Mike's army.

For each test case, print on its own line the smallest number of extra units Mike needs so that his chance of winning this turn is at least 75 percent. Print 0 if he already has at least a 75 percent chance.