Maximal GCD Query

Given n queries, each query provides four integers \(a, b, c, d\). You need to choose an integer \(x\) from the interval \([a, b]\) and an integer \(y\) from the interval \([c, d]\) and determine the maximum possible value of \(\gcd(x, y)\) among all such pairs.

The problem requires that you find the greatest integer \(k\) such that there exists at least one multiple of \(k\) in \([a, b]\) and at least one multiple of \(k\) in \([c, d]\). In mathematical terms, for a chosen \(k\), the condition can be written as:

$$\left\lfloor\frac{b}{k}\right\rfloor - \left\lfloor\frac{a-1}{k}\right\rfloor > 0 \quad\text{and}\quad \left\lfloor\frac{d}{k}\right\rfloor - \left\lfloor\frac{c-1}{k}\right\rfloor > 0.$$

inputFormat

The first line contains an integer \(n\) representing the number of queries.

Each of the following \(n\) lines contains four space-separated integers \(a\), \(b\), \(c\), and \(d\), with \(a \leq b\) and \(c \leq d\).

outputFormat

For each query, output a single line with the maximum possible \(\gcd(x,y)\) for \(x \in [a,b]\) and \(y \in [c,d]\).

sample

1
5 5 2 4

1