platinum_Transforming_Pairs (USACO February_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: state space search, number theory, euclidean algorithm, memoization

Answer $Q$ ($1\le Q\le 10^5$) independent queries each of the following form:
You are given four integers $a,b,c,d$ ($-10^{18}\le a,b,c,d\le 10^{18}$). In one
operation you can either do $a\mathrel{+}=b$,  or $b\mathrel{+}=a$. Determine
the minimum number of operations to transform $(a,b)$ into $(c,d)$, or if it is
impossible to do so, output $-1$.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $Q$.
The next $Q$ lines each contain four integers $a,b,c,d$.
OUTPUT FORMAT (print output to the terminal / stdout):
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
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|\le 10$
Input 3: $a,b\ge 0$
Input 4: $a \geq 0 \geq b$
Input 5: $a \leq 0 \leq b$
Input 6: $a,b\le 0$
Input 7: $c,d\ge 0$
Input 8: $c \geq 0 \geq d$
Input 9: $c \leq 0 \leq d$
Input 10: $c,d\le 0$
Inputs 11-14: $Q \leq 10^3$
Inputs 15-19: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: