Description

Dr. Hanks is a renowned expert in BT (Bio-Tech, 生物技术). His son is named Hankson. Now, just home from school, Hankson is thinking about an interesting problem.

Today in class, the teacher explained how to find the greatest common divisor and least common multiple of two positive integers $c_1$ and $c_2$. Now that Hankson believes he has mastered these topics, he starts considering an "inverse problem" to problems like "finding a common divisor" and "finding a common multiple". The problem is as follows: given positive integers $a_0, a_1, b_0, b_1$, let an unknown positive integer $x$ satisfy:

1. The greatest common divisor of $x$ and $a_0$ is $a_1$.
2. The least common multiple of $x$ and $b_0$ is $b_1$.

Hankson's "inverse problem" is to find all positive integers $x$ that satisfy the conditions. After a little thought, he realizes such $x$ are not necessarily unique and may even not exist. Therefore, he turns to counting how many $x$ satisfy the conditions. Please help him write a program to solve this problem.

Input Format

The first line contains a positive integer $n$, indicating there are $n$ sets of input. Each of the next $n$ lines contains one set of input: four positive integers $a_0, a_1, b_0, b_1$, separated by single spaces. It is guaranteed that $a_0$ is divisible by $a_1$, and $b_1$ is divisible by $b_0$.

Output Format

Output $n$ lines. For each set of input, output a single integer on one line.

For each set: if no such $x$ exists, print $0$; if such $x$ exist, print the number of $x$ that satisfy the conditions.

2 
41 1 96 288 
95 1 37 1776 

6 
2

Hint

• [Sample Explanation]
  • For the first set, $x$ can be $9, 18, 36, 72, 144, 288$, for a total of $6$.
  • For the second set, $x$ can be $48, 1776$, for a total of $2$.
• [Constraints]
  • For $50\%$ of the testdata, it is guaranteed that $1 \leq a_0, a_1, b_0, b_1 \leq 10000$ and $n \leq 100$.
  • For $100\%$ of the testdata, it is guaranteed that $1 \leq a_0, a_1, b_0, b_1 \leq 2 \times 10^9$ and $n \leq 2000$.

Translated by ChatGPT 5