Solar Panels

Byteasar decided to invest in renewable energy and opened a solar panel factory. Within a few days $n$ clients came in. Each client ordered one rectangular panel and gave a range for its width and a range for its height.

A panel is filled with square photovoltaic cells. A cell side length can be any positive integer, but all cells in one panel have the same side length. The larger the cells, the more efficient the panel, so for every order Byteasar wants the largest cell side length he can use.

For the $i$-th order the width is chosen as an integer in $[s_{min}, s_{max}]$ and the height as an integer in $[w_{min}, w_{max}]$. A panel of width $W$ and height $H$ can be filled with cells of side length $k$ exactly when $k$ divides both $W$ and $H$.

The first line contains one integer $n$ ($1 \le n \le 1000$), the number of ordered panels.

Each of the next $n$ lines describes one panel and contains four integers $s_{min}$, $s_{max}$, $w_{min}$, $w_{max}$ separated by single spaces ($1 \le s_{min} \le s_{max} \le 10^9$, $1 \le w_{min} \le w_{max} \le 10^9$). In order, they are the minimum width, the maximum width, the minimum height, and the maximum height of the $i$-th panel.

Print exactly $n$ lines. Line $i$ contains the largest cell side length that the $i$-th panel can be made of.

In the first example Byteasar builds panels of size $8 \times 8$ (one cell), $7 \times 14$ (two cells), $4 \times 22$ or $6 \times 22$ (22 or 33 cells), and $5 \times 20$ (four cells).