Transforming Pairs | Code Joint

Answer $Q$ ( $1 \leq Q \leq 1 0^{5}$ ) independent queries each of the following form:

You are given four integers $a, b, c, d$ ( $- 1 0^{18} \leq a, b, c, d \leq 1 0^{18}$ ). In one operation you can either do $a + = b$ , or $b + = a$ . Determine the minimum number of operations to transform $(a, b)$ into $(c, d)$ , or if it is impossible to do so, output $- 1$ .

First query: $(5, - 3) \to (2, - 3) \to (- 1, - 3)$

Second query: Impossible.

Third query: $(5, 3) \to (8, 3) \to (8, 11) \to (8, 19)$

Fourth query: No operations necessary.

SCORING:

Input 2: $∣ a ∣, ∣ b ∣, ∣ c ∣, ∣ d ∣ \leq 10$
Input 3: $a, b \geq 0$
Input 4: $a \geq 0 \geq b$
Input 5: $a \leq 0 \leq b$
Input 6: $a, b \leq 0$
Input 7: $c, d \geq 0$
Input 8: $c \geq 0 \geq d$
Input 9: $c \leq 0 \leq d$
Input 10: $c, d \leq 0$
Inputs 11-14: $Q \leq 1 0^{3}$
Inputs 15-19: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $Q$ .

The next $Q$ lines each contain four integers $a, b, c, d$ .

Output Format

The answer for each query on a separate line.

Sample Input

4 5 -3 -1 -3 5 3 5 2 5 3 8 19 5 3 5 3

Sample Output

2 -1 3 0

Submit

Language