AT_abc408_g.[ABC408G] A/B < p/q < C/D

给你四个正整数 $A,B,C,D$，满足 $\displaystyle \frac{A}{B}<\displaystyle \frac{C}{D}$。请求出最小的正整数 $q$，满足存在一个正整数 $p$ 使得 $\displaystyle \frac{A}{B}<\displaystyle \frac{p}{q}<\displaystyle \frac{C}{D}$。

可以证明这样的 $q$ 存在。多组数据。

多组数据。第一行一个整数 $T(1\le T\le 2\times 10^5)$ 表示数据组数。

对于每组数据，输入一行四个正整数 $A,B,C,D(1\le A,B,C,D\le 10^{18})$。

对于每组数据，输出一行一个整数表示答案。

样例解释

对于第一组数据，令 $p=5,q=3$，有 $\displaystyle \frac{3}{2}<\displaystyle \frac{5}{3}<\displaystyle \frac{2}{1}$，所以 $q=3$ 是可行的。

可以证明 $q$ 没有更小的正整数解，故答案为 $3$。

By @chenxi2009