Byteasar 决定投资可再生能源，于是开了一家太阳能电池板工厂。他似乎挖到了金矿，因为几天之内就有 $n$ 位客户上门。每位客户都订购了一块矩形电池板，并指定了宽度和高度的范围。

电池板由正方形光伏电池组成。这些电池有各种整数尺寸可供选择，即边长必须为整数，但同一块电池板中的所有电池必须具有相同的尺寸。生产过程具有规模经济效应，即电池尺寸越大，电池板的效率就越高。因此，对于每一块订购的电池板，Byteasar 都想知道它所能使用的电池的最大边长。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000$)，表示订购的电池板数量。接下来的 $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$ 块电池板的最小宽度、最大宽度、最小高度和最大高度。

在总分 $75\%$ 的测试点中，满足 $s_{max}, w_{max} \le 10^{7}$。在其中占总分 $20\%$ 的子任务中，额外满足 $n \le 10$。

输出格式

你的程序应向标准输出打印恰好 $n$ 行。第 $i$ 行应给出第 $i$ 块电池板所能使用的电池的最大边长。

样例

输入 1

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

输出 1

8
7
2
5

说明

Byteasar 将生产四块太阳能电池板，尺寸分别为：8x8（单个电池）、7x14（两个电池）、4x22 或 6x22（分别为 22 或 33 个电池）以及 5x20（四个电池）。