태양광 패널

바이트아사르는 재생 에너지에 투자하기로 하고 태양광 패널 공장을 차렸다. 며칠 만에 손님 $n$ 명이 찾아왔다. 손님은 각각 직사각형 패널을 하나씩 주문하면서 패널의 가로 길이 범위와 세로 길이 범위를 지정했다.

패널은 정사각형 모양의 태양전지 셀로 빈틈없이 채운다. 셀의 한 변 길이는 임의의 양의 정수가 될 수 있지만, 한 패널에 들어가는 셀은 모두 한 변 길이가 같아야 한다. 셀이 클수록 패널의 효율이 높으므로, 바이트아사르는 주문마다 쓸 수 있는 셀의 한 변 길이의 최댓값을 알고 싶다.

$i$ 번째 주문에서 가로 길이는 $[s_{min}, s_{max}]$ 안의 정수로, 세로 길이는 $[w_{min}, w_{max}]$ 안의 정수로 고른다. 가로 $W$, 세로 $H$ 인 패널을 한 변 길이 $k$ 인 셀로 채울 수 있는 것은 $k$ 가 $W$ 와 $H$ 를 모두 나누어떨어지게 할 때뿐이다.

첫째 줄에 주문된 패널의 개수 $n$ 이 주어진다 ($1 \le n \le 1000$).

다음 $n$ 개 줄에 패널이 하나씩 주어진다. $i$ 번째 줄에는 네 정수 $s_{min}$, $s_{max}$, $w_{min}$, $w_{max}$ 가 공백 한 개로 구분되어 주어진다 ($1 \le s_{min} \le s_{max} \le 10^9$, $1 \le w_{min} \le w_{max} \le 10^9$). 차례대로 $i$ 번째 패널의 가로 길이의 최솟값, 가로 길이의 최댓값, 세로 길이의 최솟값, 세로 길이의 최댓값이다.

정확히 $n$ 개 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 패널을 만들 수 있는 셀의 한 변 길이의 최댓값을 출력한다.

첫 번째 예제에서 바이트아사르는 $8 \times 8$ 패널(셀 한 개), $7 \times 14$ 패널(셀 두 개), $4 \times 22$ 또는 $6 \times 22$ 패널(셀 22개 또는 33개), $5 \times 20$ 패널(셀 네 개)을 만든다.