题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Panele słoneczne

Bajtazar 投身绿色能源，创办了一家太阳能板工厂，生意火爆！短短几天，就有 $n$ 位客户下单，每人订购一块矩形太阳能板，并指定了宽高范围。

太阳能板由正方形光伏电池组成，电池边长可为任意整数，但同一块板的所有电池必须大小相同。生产工艺决定了电池越大，板子效率越高。Bajtazar 希望为每块订购的板子确定可用的最大电池边长。请你帮他计算！

输入格式

输入第一行包含一个整数 $n$ $(1 \leq n \leq 1000)$，表示订购的太阳能板数量。

接下来的 $n$ 行描述各块板子，第 $i$ 行包含四个整数 $s_{\min}, s_{\max}, w_{\min}, w_{\max}$ $(1 \leq s_{\min} \leq s_{\max} \leq 10^9, 1 \leq w_{\min} \leq w_{\max} \leq 10^9)$，分别表示第 $i$ 块板子的最小和最大宽度、最小和最大高度。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示可用于第 $i$ 块太阳能板的最大电池边长。

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

8
7
2
5

Bajtazar 将生产四块太阳能板，尺寸分别为：$8 \times 8$（由 $1$ 个电池组成）、$7 \times 14$（由 $2$ 个电池组成）、$4 \times 22$ 或 $6 \times 22$（由 $22$ 或 $33$ 个电池组成）、$5 \times 20$（由 $4$ 个电池组成）。

附加样例

1. $n=1000, s_{\max}, w_{\max} \leq 10^7$，每块板子的最大电池边长等于 $s_{\max}$。

数据范围与提示

对于 $20\%$ 的数据，$n \leq 10$。 对于 $75\%$ 的数据，$s_{\max}, w_{\max} \leq 10^7$。