已知正整数 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$ 的范围。具体来说，我们枚举 $x$ 的值，然后检查它是否满足条件。时间复杂度为 $O(b_1)$。

接下来，我们考虑如何通过中国剩余定理求解满足条件的 $x$ 的个数。假设 $x$ 满足条件，则有：

$$
\begin{cases}
x \equiv a_0 \pmod{a_1} \\
x \equiv b_0 \pmod{b_1}
\end{cases}
$$

令 $y = b_1 / a_1$，则上述同余方程组等价于：

$$
\begin{cases}
x \equiv a_0 \pmod{a_1} \\
x \equiv b_0 \pmod{y} \\
x \equiv a_0 \pmod{y} \\
x \equiv b_0 \pmod{b_1}
\end{cases}
$$

考虑如何求解这个同余方程组。我们可以将它拆分为两个同余方程组：

$$
\begin{cases}
x \equiv a_0 \pmod{a_1} \\
x \equiv b_0 \pmod{y}
\end{cases}
\quad
\begin{cases}
x \equiv a_0 \pmod{y} \\
x \equiv b_0 \pmod{b_1}
\end{cases}
$$

分别求解这两个同余方程组，然后再合并它们的解。这个过程可以使用扩展欧几里得算法和中国剩余定理实现。

具体来说，对于第一个同余方程组，我们可以使用扩展欧几里得算法求解一个解 $x_1$。对于第二个同余方程组，我们可以使用扩展欧几里得算法求解一个解 $x_2$。然后，我们可以使用中国剩余定理求解出所有满足条件的 $x$。具体来说，设 $M = a_1 y$，则满足上述同余方程组的 $x$ 的个数为：

$$
x_2 + kM \quad (k \in \mathbb{Z})
$$

其中，$x_2$ 是第二个同余方程组的一个解，$M$ 是模数，$k$ 是待求解的系数。由于 $x_1$ 和 $x_2$ 的解都满足同余方程组，因此它们的差 $x_2 - x_1$ 必然是 $M$ 的倍数。因此，我们只需要枚举 $k$ 的范围，并检查 $x_2 + kM$ 是否满足第一个同余方程组即可。

时间复杂度为 $O(n \log n)$。

下面是一份 C 语言代码，用于解决这个问题：

#include <stdio.h>

int gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1, g;
    g = gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

int main() {
    int n, a0, a1, b0, b1;
    int x1, y1, x2, y2, g, k1, k2, count, M, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        if (b1 % a1 != 0 || a0 % a1 != 0 || b0 % (b1 / a1) != 0) {
            printf("0\n");
            continue;
        }
        int y = b1 / a1;
        int z = a0 / a1;
        int w = b0 / y;
        g = gcd(z, gcd(y, w), &x1, &y1);
        z /= g;
        y /= g;
        w /= g;
        g = gcd(y, w, &x2, &y2);
        M = y * w;
        count = 0;
        for (k1 = 0; k1 < g; k1++) {
            for (k2 = 0; k2 < z; k2++) {
                x = x2 + k1 * y;
                if ((x - x1) % z == 0) {
                    count++;
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

注意，由于本题数据范围较大，需要开启编译器的 O2 优化选项才能通过本题。