Eric has four integers $a$, ${b}$, ${c}$, and ${d}$.

Instantly, he wondered how many pairs of integers, $(x,y)$, satisfy the following equation:

$x^2+y^2=(x\times a)+(y\times b)$

where $1\leq x\leq c$ and $1\leq y\leq d$.

Find and print the number of pairs that satisfy the above equation.

Input Format

The first line contains an integer ${q}$, the number of queries.

${q}$ lines follow, each containing four integers, ${a}$, ${b}$, ${c}$, and ${d}$, in that order.

Constraints

$1\leq q\leq10$
$1\leq a,b,c,d\leq10^5$

Output Format

For each test case, print one line, the number of pairs $(x,y)$ that are valid solutions to Eric's equation.

Sample Input 0
1
1 1 1 1

Sample Output 0
1

Explanation 0

The solution to $x^2+y^2=x+y$, where $1\leq x\leq1$ and $1\leq y\leq1$ is $x=1$, $y=1$.

见题面

见题面