# 描述

There is an interesting and simple one person game. Suppose there is a number axis under your feet. You are at point $A$ at first and your aim is point $B$. There are 6 kinds of operations you can perform in one step. That is to go left or right by $a,b$ and $c$, here $c$ always equals to $a+b$.

You must arrive B as soon as possible. Please calculate the minimum number of steps.

## Input

There are multiple test cases. The first line of input is an integer $T(0 < T ≤ 1000)$indicates the number of test cases. Then T test cases follow. Each test case is represented by a line containing four integers 4 integers$A, B, a\$and $b$, separated by spaces. ($-2^{31} ≤ A, B < 2^{31}, 0 < a, b < 2^{31}$)

## Output

For each test case, output the minimum number of steps. If it’s impossible to reach point B, output “-1” instead.

• intput

• output

# 思路

• 一开始以为是道bfs，敲到一半看到数据范围就发现天真了。
• 题目其实就是求$|C_1a+C_2b+C_3c+C_4(-a)+C_5(-b)+C_6(-c)|=|A-B|$，化简之后就变成了$|C_1a+C_2b|=|A-B|$，还是不满足拓展欧几里德的形式。要变形一下就变成了
• 我们还知道拓展欧几里德的通解是$x=x_0+(b/gcd)\cdot t$，$y=y_0-(a/gcd)\cdot t$，($y_0$和$x_0$为一组特解)。这时候我们带出$C_1,C_2$，画出$C_1,C_2$关于$t$的两条直线，显然当$x,y$异号的时候，$ans=|x+y|$，当$x,y$同号的时候，$ans=max(|a|,|y|)$,结合图像，显然交点为最优解。但交点对应的$t$不一定是整数点，所以我们在对$t$取整后还要比较$t$取$t+1$时的情况。
• 拓展欧几里德详见：数论笔记本

# 代码

-------------本文结束 感谢您的阅读-------------