Description

For $n$ queries, each query is given four integers $a, b, c, d$. Choose any two integers $x$ and $y$ from the intervals $[a, b]$ and $[c, d]$, respectively, and find the maximum possible value of $\gcd(x, y)$.

Input Format

The first line contains an integer $n$ representing the number of queries.
The next $n$ lines each contain a query: four integers $a, b, c, d$ specifying the two intervals.

Output Format

Output $n$ lines, each containing a single integer: the maximum possible value of $\gcd(x, y)$ when choosing $x$ from $[a, b]$ and $y$ from $[c, d]$.

4
3 9 8 8
1 10 11 15
4 7 22 23
2 5 19 24

8
7
2
5

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le a \le b \le 10^9$, $1 \le c \le d \le 10^9$.

Notes

Translated by @一只书虫仔。

Translated by ChatGPT 5