P6913 [ICPC 2015 WF] Tile Cutting

Youssef 是一名专业贴瓷砖的修墙工，并且擅长用瓷砖贴出马赛克图案（如上图所示）。所有的瓷砖的尺寸长度均为整数，单位为 $cm$。在马赛克图案中，平行四边形是不可或缺的。因此，Youssef 会使用切割机，将矩形的瓷砖进行切割。在切割过程中，Youssef 选择使用网格辅助切割机进行切割（在瓷砖上布上 $cm$ 的网格方便切割）。 切割过程有以下要求： 1. 可以从两个不同端点的连线切割（可以斜着切割） 2. 新平行四边形的四个角必须在矩形瓷砖的最外侧边上 3. 平行四边形的边不能与矩形的任意一条边边重叠 现在给出切割的面积的两个边界值 $a_{lo}$ 和 $a_{hi}$，求出 Youssef 能够最多切割掉的小矩形瓷砖数量。

给出测试样例数量$n$($1≤n≤500$)。下面$n$行给出切割面积的两个边界值$a_{lo}$和$a_{hi}$（$1≤a_{lo}≤a_{hi}≤500 000$）

每行先输出平行四边形面积$a$，再输出小矩形最多切割数量$w$。如果$a$有不同值的时候，输出最小的即可。

Time limit: 11000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2015