UVA1718 Tile Cutting

Youssef 是一名摩洛哥的瓷砖安装工人，专门从事右图中展示的马赛克瓷砖的安装工作。他有各种尺寸的矩形瓷砖可以使用，而且他的所有瓷砖的尺寸都是以厘米为单位的整数。当 Youssef 需要平行四边形形状的瓷砖时，他会从手头的存货中切割出来。为了使这个工作更容易，他发明了一台瓷砖切割机，该机器在切割面上叠加了一个厘米网格，以指导对瓷砖的切割。由于机器的限制、审美观和 Youssef 不喜欢浪费瓷砖，以下规则限制了可能的切割方式。 1. 要切割的矩形瓷砖必须位于切割面的左下角，并且边缘必须与网格线对齐。 2. 只要两个不同网格点位于相邻的边界边上，切割刀就可以沿着连接这两个点的任意线段方向进行切割。 3. 最终得到的平行四边形瓷砖的四个角必须位于原始矩形瓷砖的四条边上。 4. 平行四边形瓷砖的任何一条边都不能与矩形瓷砖的边重合。 图 $J.1$ (见原题面)展示了按照上述限制条件切割出一个面积为 $4$ 平方厘米的平行四边形瓷砖的八种不同方式。

输入包含多组数据。第一行输入包含一个整数 $n$ $(1\le n \le 500)$，表示数据组数。接下来的 $n$ 行，每行读入两个整数 $a_{l_o}$ 和 $a_{h_i}$ $(1 \le a_{l_o} \le a_{h_i} \le 500000)$，表示瓷砖面积的范围。

对于每组数据的 $a_{l_o}$, $a_{h_i}$，输出一个介于 $a_{l_o}$ 和 $a_{h_i}$ 之间的值 $a$，使得切割出的平行四边形瓷砖的切割方式数量最大化，并且不同切割方式的数量 $w$ 也最大化。如果存在多个符合要求的值 $a$，则输出最小的一个。