Background

How many bends the river has, how many layers the mountains pile, where is the city of Jinling.
Visit the famous capital, seek its fine scenery, the Dragon and Tiger lean on the east of the Yangtze.
Ink remains on the page, melodies fall with the sound of tides.
Plants and trees wither and flourish again and again.

— Yinlin, “Ballad of Jinling”

Problem Description

Nanjing in Jiangsu, also known as Jinling, is a famous historical and cultural city. With the old city as a backdrop, even Jiangsu’s Gaokao mock exam problems look very tricky and hard to solve. During the first round of review, Qieqie ran into a mock problem from Jiangsu Province. With the help of Qijin, Qieqie quickly solved it instantly, but Qieqie still felt it was not enough and wants to use this problem to make things difficult for you. Solving this problem will let you taste the “sweetness” sprinkled by Qieqie and Qijin.

Given four positive integers $a, b, c, d$, find how many pairs of positive integers $(x, y)$ satisfy

Input Format

This problem contains multiple groups of testdata in a single test case.

The first line contains an integer, representing the number of groups $T$.

The next $T$ lines each contain four integers, representing one group of data: $a, b, c, d$ in order.

Output Format

For each group of data, output one integer per line representing the answer.

1
1 1 3 2

3

Hint

Sample 1 Explanation

Find the number of positive integer solution pairs of $\frac 1 x + \frac 1 3 = \frac 2 y$. They are $(x = 3, y = 3)$, $(x = 6, y = 4)$, $(x = 15, y = 5)$.

Constraints

This problem has 20 test points, and each test point is worth $5$ points.

• For test point $1$, it is guaranteed that $T = 0$.
• For test points $2 \sim 16$, there are $15$ test points in total. Among the four numbers $a, b, c, d$, there is guaranteed to be at least one number equal to $1$. There are $15$ such cases, and each test point corresponds to one case.
• For test points $17 \sim 20$, there are no special constraints.

For all test points, it is guaranteed that $0 \leq T \leq 20$, $1 \leq a, b, c, d \leq 10^6$, and $d \times c \leq 10^6$.

Notes

• As everyone knows, Gaokao does not test number theory.
• This problem provides two sample files. See song.zip in the attachments.

Translated by ChatGPT 5