Answer Q(1≤Q≤105) independent queries each of the following form:
You are given four integers a,b,c,d(−1018≤a,b,c,d≤1018). 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.
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)→(2,−3)→(−1,−3)
Second query: Impossible.
Third query: (5,3)→(8,3)→(8,11)→(8,19)
Fourth query: No operations necessary.
SCORING:
Input 2: |a|,|b|,|c|,|d|≤10
Input 3: a,b≥0
Input 4: a≥0≥b
Input 5: a≤0≤b
Input 6: a,b≤0
Input 7: c,d≥0
Input 8: c≥0≥d
Input 9: c≤0≤d
Input 10: c,d≤0
Inputs 11-14: Q≤103
Inputs 15-19: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
