已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足： 1． x 和 a0 的最大公约数是 a1 2． x 和 b0 的最小公倍数是 b1 求解满足条件的 x 的个数。请你帮助他编程求解这个问题。 对于 100%的数据，保证有 1≤a0，a1，b0，b1≤2,000,000,000。 输入格式: 第一行为一个正整数 n，表示有 n 组输入数据。n≤2000 接下来的 n 行每行一组输入数据，为四个正整数 a0，a1，b0，b1，之间用一个空格隔开。 输出格式: 共n 行。每组输入数据的输出结果占一行，为一个整数。 对于每组数据：若不存在这样的 x，请输出 0； 若存在这样的 x，请输出满足条件的 x 的个数； 输入样例: 在这里给出一组输入。例如： 2 41 1 96 288 95 1 37 1776 输出样例: 在这里给出相应的输出。例如： 6 2 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这个问题可以转化为求 $x$ 满足两个条件：

$$
\begin{aligned}
\text{gcd}(x,a_0) &= a_1 \\
\text{lcm}(x,b_0) &= b_1
\end{aligned}
$$

我们可以先求出 $\gcd(a_0,b_0)$ 和 $\text{lcm}(a_0,b_0)$，分别记作 $d$ 和 $m$。那么对于 $\text{gcd}(x,a_0)=a_1$，我们可以得到 $a_1$ 必须是 $d$ 的倍数，否则无解。即：

$$
a_1 \mid d
$$

对于 $\text{lcm}(x,b_0)=b_1$，我们可以得到 $b_1$ 必须是 $m$ 的倍数，否则无解。即：

$$
b_1 \mid m
$$

接下来我们考虑如何求解 $x$ 的个数。假设 $x = q_1 a_1 d = q_2 b_1 m$，其中 $q_1,q_2$ 是正整数。由于 $a_1$ 和 $b_1$ 互质，所以可以得到 $x$ 的一般形式：

$$
x = q_1 a_1 d + q_2 b_1 m
$$

我们要求的是满足条件的 $x$ 的个数，即满足 $\text{gcd}(x,a_0)=a_1$ 和 $\text{lcm}(x,b_0)=b_1$ 的 $x$ 的个数。考虑到 $a_1$ 和 $b_1$ 都是 $d$ 和 $m$ 的因子，所以我们可以枚举 $a_1$ 和 $b_1$ 的公共因子 $s$，然后求解 $q_1$ 和 $q_2$ 的方程：

$$
\begin{aligned}
q_1 a_1 d + q_2 b_1 m &= x \\
\frac{q_1 d}{s} \cdot \frac{a_1}{s} + \frac{q_2 m}{s} \cdot \frac{b_1}{s} &= \frac{x}{s}
\end{aligned}
$$

这是一个二元一次方程组，可以使用扩展欧几里得算法求解。具体地，我们要求解的是形如 $ax+by=c$ 的方程，其中 $a,b,c$ 是已知的整数。我们可以先求解 $\gcd(a,b)$，如果 $c$ 不能被 $\gcd(a,b)$ 整除，那么该方程组无解。否则，我们可以使用扩展欧几里得算法求解 $ax+by=\gcd(a,b)$ 的一组解 $(x_0,y_0)$，然后可以得到该方程组的一般解：

$$
\begin{aligned}
x &= x_0 \cdot \frac{c}{d} + \frac{b}{d} \cdot k \\
y &= y_0 \cdot \frac{c}{d} - \frac{a}{d} \cdot k
\end{aligned}
$$

其中 $d=\gcd(a,b)$，$k$ 是任意整数。我们可以把 $k$ 的范围限制在 $0 \leq k \leq \frac{s}{\gcd(\frac{a}{s},\frac{b}{s})}$，这样可以保证 $\frac{q_1 d}{s}$ 和 $\frac{q_2 m}{s}$ 都是正整数。具体的实现可以参考下面的代码：